Extracting k-th roots mod m

[Dubslow]

That is, given k, b, m, finding an x that satisfies .

Originally Posted by Dubslow

Hello Professor,

I missed last Monday's MATH 453 lecture (3/12/12) on k-th roots mod m, and so I was reading the notes you graciously put online. I implemented the algorithm described, which I had seen before in the RSA appendix of the textbook.

I read through the notes, and constructed a very similar proof of the algorithm's correctness; originally, however, I didn't see where the restriction (b, m) = 1 came from. (I've since realized that it's a required hypothesis to apply Euler's theorem to b^(ku-1).) So, in my ignorance, I started looking at some test cases to determine if/when the algorithm worked without that restriction. To my surprise, more often than not, the algorithm succeeds at finding the proper k-th root modulo m when (b, m) > 1, even though that fact is crucial in applying Euler's theorem.

So, I wrote another function that would create random triplets of k, b, and m, attempt to find the corresponding root, and then record whether or not the algorithm failed or succeeded. (If (k, phi) > 1, then that triplet is ignored.)

In a test of 100,000 random triplets (with (k,phi) = 1), there were 60,012 triplets with (b,m)=1, and thus the algorithm automatically worked; 7544 zero-results, where the algorithm returned 0, 8402 results where the algorithm returned a non-zero result that was wrong, and 24042 results where (b,m) > 1 but somehow the algorithm worked, to my astonishment (after I realized why (b,m)=1 is theoretically a necessary condition). So, out of ~40,000 test cases with (b,m) > 1, around 60% of the time, the algorithm succeeded anyways.

So my question is, do you know any other algorithm for computing k-th roots modulo m, since clearly the algorithm presented in the textbook/notes is not always capable of finding a solution that does exist? Do you know of a way to prove when a solution doesn't exist? Do you know why this algorithm works even when it shouldn't? (I did look at a few specific cases, and in none of those was Euler's theorem "accidently" true, i.e. b^(ku-1) was not congruent to 1, but it still got the right answer.)

(The code I wrote is here. You can find the "support" functions, e.g. phi() and invert(), here, though without the fancy syntax highlighting.)

Thanks,
Bill

Dear Bill,
The situation when gcd(b,m)>1 (and even gcd(k,phi(m))>1 !!!) is indeed tricky. One can show (not using Euler's formula directly) that if m is a product of distinct primes, then x==b^u mod m is always a solution to x^k==b mod m, even if gcd(b,m)>1. My guess is that this is the reason why the algorithm works in more cases than expected. To be honest, I don't know on the top of my head if this exhausts all the cases where the algorithm works. Can you check whether the cases where the algorithm works all come from m that are product of distinct primes (that is squarefree)?
Regards,
[Prof]

Hello Professor,

I just added in that check; just under two thirds (64%) of the cases where the algorithm produced the correct answer [for (b,m) > 1] were cases where m was square free; that leaves the other third as yet unexplained.

Thanks again,
Bill

So, same question for all you smart people. How does it work?

Based on some Googling, I have a feeling I should read the chapter on order of an int mod m, which we won't really be covering in class...

[LaurV]

Originally Posted by Dubslow

That is, given k, b, m, finding an x that satisfies .

Did not go through all your text yet (job) but the common sense tells me this is solvable only for a thin number of particular cases and/or for prime modulus. If it won't be that, i.e. we have a way to solve this efficiently for a general case, then we just have to take k=2 (any even would do it), b=1 (any square) and m any hard to factor composite, find the right x (a nontrivial solution) and factor m efficiently with congruence of squares.

[Dubslow]

Well, since this thread went no where fast, I'll recycle it to ask another question.


Context: Fermat's prp test isn't very effective, because there exist numbers which are false primes for every possible base, and, (since 1994) there are infinitely many such numbers.

However, there exists a similar but less-talked-about test for compositeness, namely that of kidnapping Euler's criterion, which (among other things) implies that if p is an odd prime, then a^(p-1)/2 is congruent to +-1 mod p (for every a which p does not divide). In particular, if we are given a number n and we find some a where a^(n-1)/2 =/= +-1 mod n, then n is surely composite. (Side note: calculating this power is even less intensive than the Fermat power )

So, this "Euler prp" (analogous to "Fermat prp") does not (that I know of) have a large quantity of pseudoprimes (to every base). Clearly, if there were no such pseudoprimes, we would have a very efficient linear time primality test, so it seems to me, someone must have investigated this before. Does anybody know what results there are on this matter? (It also seems to me every Carmichael number fails this Euler prp test would be a significant theoretic achievement.)

(Yes, I am aware that there are much stronger prp tests such as Miller-Rabin, but we never got to it in my Number Theory course. I'll look into it shortly.)

[axn]

http://en.wikipedia.org/wiki/Euler%E...bi_pseudoprime

[LaurV]

Originally Posted by Dubslow

there exist numbers which are false primes for every possible base, and, (since 1994) there are infinitely many such numbers.

[ot]
Are you sure that before 1994 there weren't infinitely many such numbers?
[/ot]

[Dubslow]

Originally Posted by axn

http://en.wikipedia.org/wiki/Euler%E...bi_pseudoprime

Neat, thanks!

For whatever reason, neither that nor "Euler pseudoprime" (a separate article describing what I did) were linked to from the Euler criterion page that I'd been reading. Of interest is that there are no absolute Euler-Jacobi pseudoprimes.

[axn]

Originally Posted by LaurV

[ot]
Are you sure that before 1994 there weren't infinitely many such numbers?
[/ot]

Oh, there were... absolutely. It is just that, they came out of the closet only in 1994 (if I'm not mistaken)

[Dubslow]

Originally Posted by axn

Oh, there were... absolutely. It is just that, they came out of the closet only in 1994 (if I'm not mistaken)

Yep, that's when the proof was published.


After more reading, it seems to me that what I really ran across was the second tier in a four-level hierarchy of PRP tests based on power congruences mod p.

Fermat test -> Euler test -> Euler-Jacobi/Solovay–Strassen test -> Miller-Rabin test, where each is a modest improvement over the former.

[ewmayer]

IIRC, all these refinements are intended to boost the odds that (aasuming the result of the mod-poering is 1, or +-1 in the case of Euler's criterion) the candidate seed a is a primitive root (= of order n-1, implying that n is prime), rather than a root of order < n-1.

I seem to recall that the practical issue with Euler's criterion is determining the proper +- sign of the right-hand-side 1, via evaluation of the Jacobi symbol.