mersenneforum.org > Math Mod question in N-1 primality test
 Register FAQ Search Today's Posts Mark Forums Read

 2023-02-04, 07:29 #1 wblipp     "William" May 2003 Near Grandkid 237410 Posts Mod question in N-1 primality test The classic paper on N+/-1 primality tests is Brillhart, Lehmer, and Selfridge 1975. I need help understanding part of Remark 4 of Theorem 5. At this point N-1 has been partially factored as F*R, with F fully factored. We know from a previous theorem that if N is composite, it is (c*F+1)*(d*F+1). Part of Remark 4 says that if N = -1 (mod 5) and it is known that 5 is a quadratic residue of N, then since 5 does not divide F, 5 divides c*d. I think this should be understood as meaning "5 divides c*d*F". But why? When working mod 5, you can get -1 from 2*2 or 3*3 in addition to 1*(-1) and (-1)*1, so you can't just say one of the factors is 1 (mod 5). The "known to be a quadratic residue" must be useful somehow, but how?
 2023-02-04, 13:07 #2 charybdis     Apr 2020 13×73 Posts If 5 is a quadratic residue mod N, then it is also a quadratic residue mod each of the factors of N. But (5|cF+1) = (cF+1|5) by quadratic reciprocity, so if cF+1 is not a square mod 5 (i.e. it is 2 or 3 mod 5), then 5 is not a square mod cF+1. Same goes for dF+1. Note this doesn't assume cF+1 and dF+1 are prime: quadratic reciprocity holds for Jacobi symbols, and the Jacobi symbol (m|n) = -1 still implies m is not a quadratic residue mod n.
 2023-02-09, 11:52 #3 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 32×673 Posts Am I being brain-dead or is there a potential factorisation method here(not necessarily a good one)? For composite N find factors of N-1 that satisfy Theorem 4. These factors make up the fully factored part F. We know that N = (c*F+1)*(d*F+1) but don't know c and d. Now find a list of primes that N = -1 (mod p) and p is a quadratic residue of N. These primes divide c*d and can be used to help find c and d. If we have c and d we have a factorisation of N. Potential problems: This method will be easier with large F. Note F will always be less than sqrt(N) as otherwise, N will be prime. No factors can be found that are smaller than F. Determining if p is a quadratic residue of N is pretty much impossible without knowing the factors of N. Primes could be found by squaring numbers modulo N but N is unlikely to be -1 mod p. It may be difficult to find factors of N-1. The number of primes that we can determine of factors of c*d may too small to make finding c and d possible. It looks like this method stands a vague chance of working on numbers generated such that there are many known factors of N-1 and primes that are quadratic residues of N and N = -1 mod p. Is it possible to generate numbers where N-1 and N+1 have many known factors and the prime factors of N+1 are quadratic residues mod N? Note that knowing factors of x*N+1 meeting these conditions is sufficient. It is worth noting that if we can find numbers that are probably factors of c*d then these could be used as prompts for the P-1 method. This is probably completely useless but there may be someone interested.
2023-02-09, 13:16   #4
charybdis

Apr 2020

11101101012 Posts

Quote:
 Originally Posted by henryzz Am I being brain-dead or is there a potential factorisation method here(not necessarily a good one)? For composite N find factors of N-1 that satisfy Theorem 4.
One of the conditions of Theorem 4 is that N is a pseudoprime to base ai. How do you propose to find such a base without knowing the factorization of N?

Last fiddled with by charybdis on 2023-02-09 at 13:47 Reason: removed some rubbish

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 a1call Miscellaneous Math 29 2018-12-24 01:42 Trilo Miscellaneous Math 25 2018-03-11 23:20 Citrix Math 3 2005-09-19 15:06 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 11:53.

Thu Mar 30 11:53:17 UTC 2023 up 224 days, 9:21, 0 users, load averages: 0.91, 0.80, 0.81