mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2012-12-10, 04:00   #1
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default 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
Dubslow is offline   Reply With Quote
Old 2012-12-10, 05:49   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×11×397 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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.
LaurV is offline   Reply With Quote
Old 2012-12-13, 06:34   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default

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.)
Dubslow is offline   Reply With Quote
Old 2012-12-13, 07:40   #4
axn
 
axn's Avatar
 
Jun 2003

13·192 Posts
Default

http://en.wikipedia.org/wiki/Euler%E...bi_pseudoprime
axn is offline   Reply With Quote
Old 2012-12-13, 07:41   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

873410 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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]
LaurV is offline   Reply With Quote
Old 2012-12-13, 07:57   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C3516 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2012-12-13, 08:41   #7
axn
 
axn's Avatar
 
Jun 2003

125516 Posts
Default

Quote:
Originally Posted by LaurV View Post
[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)
axn is offline   Reply With Quote
Old 2012-12-13, 20:09   #8
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by axn View Post
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.
Dubslow is offline   Reply With Quote
Old 2012-12-13, 21:35   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×13×443 Posts
Default

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
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Extracting the Modulus from publickeyblob RSA 512 26B Homework Help 2 2014-11-30 07:31
Roots of 1 mod 2^n fenderbender Miscellaneous Math 17 2010-11-16 16:25
bash script for extracting primenet-status gLauss Linux 0 2010-07-31 11:19
Extracting factors from ECMNet amcfarlane GMP-ECM 4 2006-05-19 18:03
What is the roots of NFS algorithm? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.