Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If we're given two naturals, $a$ and $b$, and a prime $p$, how fast can we find two more naturals such that $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$?

Additionally, you are allowed to precompute anything you like, but the memory space you are given can be no larger than the time it takes to solve this problem. In other words, how fast can we solve for these two variables in equal time and space?

share|improve this question
    
gcd(a,b) can be found in polynomial time. –  Dan Brumleve Sep 30 '11 at 7:14
    
Specifying that you can "precompute anything you like" makes little sense without a division of the inputs into early ones and late ones. If all inputs are early, you can just precompute the entire answer and give that immediately when asked to start the "real" computation. –  Henning Makholm Sep 30 '11 at 7:56
    
I recently answered essentially this same question: math.stackexchange.com/questions/67171/… –  Michael Hardy Oct 1 '11 at 4:26
add comment

3 Answers 3

up vote 1 down vote accepted

As Greg Martin points out, you cannot do this, if $a$ and $b$ are both divisible by $p$. So assume that at least one of them, say $a$, is not divisible by $p$. In that case you can select $d$ any which way you want (IOW the system is underdetermined). Here's how:

1) (Pre)compute a modular inverse of $a$. This is an integer with property $aa'\equiv1\pmod p$. It can be found by a single run of an extended Euclidean algorithm. If the same $a,p$ are used many times, then we can obviously store the result for future reuse.

2) Compute the integer $c=a'(1+bd) \pmod p$, and lean back content. Here's why that works $$ a\cdot c=a\cdot a'(1+bd)\equiv 1+bd\pmod p, $$ because $a\cdot a'\equiv 1\pmod p$. That congruence is clearly equivalent to the desired congruence (move the term $bd$ to the other side and swap its sign).

===============================

IOW, if $(a,p)=1$ (or $(b,p)=1$), then what you have is essentially a single linear equation in two variables with parameters ranging over the field $\mathbf{Z}_p.$ Under such circumstances you can choose one of the unknowns arbitrarily and solve for the other. There will be exactly $p$ pairwise non-congruent solutions.

share|improve this answer
add comment

First of all, you won't always be able to find such integers $c$ and $d$: it's possible that both $a$ and $b$ are divisible by $p$.

Assume then that $p$ does not divide $a$ (exchanging $a$ and $b$ if necessary). Then $\gcd(a,p)=1$, so the extended Euclidean algorithm calculates numbers $c$ and $y$ such that $ac+py=1$; you can simply take this $c$ and $d=0$. The extended Euclidean algorithm runs extremely quickly - linear in the size of the input $(a,p)$.

It's conceivable that the extra degree of freedom you have in the initial problem (you can vary both $c$ and $d$) would lead to a faster algorithm, but I doubt it - the Euclidean algorithm is lightning fast in practice.

Finally, you don't really need $p$ to be a prime: such integers $c$ and $d$ exist if and only if $\gcd(a,b,p)=1$. (If $a,b,p$ are not pairwise disjoint then you would need to run the Euclidean algorithm more than once, say on $a$ and $b$ first and then on $\gcd(a,b)$ and $p$.)

share|improve this answer
add comment

I recently answered essentially this same question: Calculating the Modular Multiplicative Inverse without all those strange looking symbols

It was phrased differently: It asked how to find the mod-$p$ multiplicative inverse of a number that is not a multiple of $p$ (i.e. is not the same as $0$ in mod $p$).

Exactly the same algorithm works for a non-prime, provided only that the modulus and the number whose inverse is sought have no prime factors in common.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.