20121210, 04:00  #1  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1110000110101_{2} Posts 
Extracting kth roots mod m
That is, given k, b, m, finding an x that satisfies .
Quote:
Quote:
Quote:
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 20121210 at 04:05 Reason: damn tex cant space itself 

20121210, 05:49  #2 
Romulan Interpreter
Jun 2011
Thailand
9275_{10} Posts 
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.

20121213, 06:34  #3 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1C35_{16} Posts 
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 lesstalkedabout test for compositeness, namely that of kidnapping Euler's criterion, which (among other things) implies that if p is an odd prime, then a^{(p1)/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^{(n1)/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 MillerRabin, but we never got to it in my Number Theory course. I'll look into it shortly.) 
20121213, 07:40  #4 
Jun 2003
4,861 Posts 

20121213, 07:41  #5 
Romulan Interpreter
Jun 2011
Thailand
5^{2}·7·53 Posts 

20121213, 07:57  #6  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:
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 EulerJacobi pseudoprimes. 

20121213, 08:41  #7 
Jun 2003
4,861 Posts 

20121213, 20:09  #8  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:
After more reading, it seems to me that what I really ran across was the second tier in a fourlevel hierarchy of PRP tests based on power congruences mod p. Fermat test > Euler test > EulerJacobi/Solovay–Strassen test > MillerRabin test, where each is a modest improvement over the former. 

20121213, 21:35  #9 
∂^{2}ω=0
Sep 2002
República de California
2^{5}×3×11^{2} Posts 
IIRC, all these refinements are intended to boost the odds that (aasuming the result of the modpoering is 1, or +1 in the case of Euler's criterion) the candidate seed a is a primitive root (= of order n1, implying that n is prime), rather than a root of order < n1.
I seem to recall that the practical issue with Euler's criterion is determining the proper + sign of the righthandside 1, via evaluation of the Jacobi symbol. Last fiddled with by ewmayer on 20121213 at 22:27 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Extracting the Modulus from publickeyblob RSA 512  26B  Homework Help  2  20141130 07:31 
Roots of 1 mod 2^n  fenderbender  Miscellaneous Math  17  20101116 16:25 
bash script for extracting primenetstatus  gLauss  Linux  0  20100731 11:19 
Extracting factors from ECMNet  amcfarlane  GMPECM  4  20060519 18:03 
What is the roots of NFS algorithm?  Annunaki  NFSNET Discussion  7  20030729 16:01 