mersenneforum.org Extracting k-th roots mod m
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2012-12-10, 04:00   #1
Dubslow
Basketry That Evening!

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

11100001101012 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

927510 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 4,861 Posts
2012-12-13, 07:41   #5
LaurV
Romulan Interpreter

Jun 2011
Thailand

52·7·53 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
Basketry That Evening!

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

3·29·83 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

4,861 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
Basketry That Evening!

"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 25×3×112 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

 Thread Tools

 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 11:56.

Tue Mar 9 11:56:24 UTC 2021 up 96 days, 8:07, 0 users, load averages: 1.96, 1.56, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.