- Jul 6, 2014The other day I was browsing through Riesel and opened it at Appendix
3, Legendre’s symbol,
x^2 º a mod p; a thought came into my mind from where who knows!!
It was just silly, that it was equivalent to N = pq.
An odd p < s (s the integer square root) will be a factor of N a
composite odd number if and only if
s^2 = - (N - s^2) mod p .
I can prove the main part but not that p can be either a prime or a
N = pq
s = flr(sqr( N))
Redefine p and q as follows:-
p = s - t ( t is an integer - 0 < t < s )
q = s + t + k ( k is an integer and will always be of the form of
either (0 mod 4) or (2 mod 4) depending on N
Substituting the redefined p and q , back into N = pq
N = ( s - t)( s + t + k)
N = s^2 + ks - kt - t^2 (the st values cancel out)
Solve for t^2
t^2 = k(s - t) - (N - s^2)
Taking the modulus of both sides using (s - t) gives
t^2 = 0 - ( N - s^2) (mod ( s - t))
t^2 mod(s - t) = s^2 mod ( s- t) (any difference is a multiple of ( s
s^2 = - ( N - s^2) mod p.
I will use a number from Riesel (page 147 of my edition)
N = 13199
s = 114
p = 67
(114^2) mod 67 = 65
(N - s^2) = 203 => 203 mod 67 = 2
This is 67 - 2 = 65
I have looked at some of the RSA numbers that have been solved and they
also confirm the above.
A number that shows that p can be composite is 1617
N = 1617
s = 40
p = 33
(40^2) mod 33 = 16
N - s^2 = 1617 - 1600 = 17
p - 17 = 33 - 17 = 16
If the residues to a number N, are found using the N and then (N-s^2)
they give 2 different sets; example using 12007001
Residues for N =? (-1 2 3 5 7 11 13 23 29 37 43 71 73 89 97)
Residues for (N - s^2) => (-1 2 5 23 31 43 53 59 61 67 71 89 97)
Intersection of the 2 sets gives (-1 2 5 23 43 71 89 97)
I am not sure that this will be of any real benefit, but who knows.
- << Previous post in topic Next post in topic >>