mersenneforum.org Extracting k-th roots mod m
 Register FAQ Search Today's Posts Mark Forums Read

2012-12-10, 04:00   #1
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Extracting k-th roots mod m

That is, given k, b, m, finding an x that satisfies $x^k \equiv b\quad mod\quad m$.
Quote:
 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
Quote:
 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]
Quote:
 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...

Last fiddled with by Dubslow on 2012-12-10 at 04:05 Reason: damn tex cant space itself

2012-12-10, 05:49   #2
LaurV
Romulan Interpreter

Jun 2011
Thailand

2×11×397 Posts

Quote:
 Originally Posted by Dubslow That is, given k, b, m, finding an x that satisfies $x^k \equiv b\quad mod\quad m$.
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.

 2012-12-13, 06:34 #3 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2012-12-13, 07:40 #4 axn     Jun 2003 13·192 Posts
2012-12-13, 07:41   #5
LaurV
Romulan Interpreter

Jun 2011
Thailand

873410 Posts

Quote:
 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]

2012-12-13, 07:57   #6
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C3516 Posts

Quote:
 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.

2012-12-13, 08:41   #7
axn

Jun 2003

125516 Posts

Quote:
 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)

2012-12-13, 20:09   #8
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 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.

 2012-12-13, 21:35 #9 ewmayer ∂2ω=0     Sep 2002 República de California 2×13×443 Posts 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. Last fiddled with by ewmayer on 2012-12-13 at 22:27

 Similar Threads Thread Thread Starter Forum Replies Last Post 26B Homework Help 2 2014-11-30 07:31 fenderbender Miscellaneous Math 17 2010-11-16 16:25 gLauss Linux 0 2010-07-31 11:19 amcfarlane GMP-ECM 4 2006-05-19 18:03 Annunaki NFSNET Discussion 7 2003-07-29 16:01

All times are UTC. The time now is 10:19.

Sat Sep 19 10:19:13 UTC 2020 up 9 days, 7:30, 0 users, load averages: 1.41, 1.56, 1.59