Mod question in N-1 primality test

[wblipp]

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?

[charybdis]

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.

[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.
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.

[charybdis]

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 a_i. How do you propose to find such a base without knowing the factorization of N?