2023-02-04, 07:29 | #1 |
"William"
May 2003
Near Grandkid
2374_{10} 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 |
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 |
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
3^{2}×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 |
Apr 2020
1110110101_{2} Posts |
One of the conditions of Theorem 4 is that N is a pseudoprime to base a_{i}. 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 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
I found the primality test, there seems to be no composite numbers that pass the test | sweety439 | sweety439 | 7 | 2020-02-11 19:49 |
+/- 6 Primality Test | a1call | Miscellaneous Math | 29 | 2018-12-24 01:42 |
Modifying the Lucas Lehmer Primality Test into a fast test of nothing | Trilo | Miscellaneous Math | 25 | 2018-03-11 23:20 |
N-1 primality test | Citrix | Math | 3 | 2005-09-19 15:06 |
A primality test for Fermat numbers faster than Pépin's test ? | T.Rex | Math | 0 | 2004-10-26 21:37 |