Loading ...
Sorry, an error occurred while loading the content.

25573Conjecture

Expand Messages
  • ronhallam@lineone.net
    Jul 6, 2014
    • 0 Attachment
      The 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.



      Conjecture

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

      Proof

      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
      - t))



      This gives



      s^2 = - ( N - s^2) mod p.

      QED



      Example

      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.





      Ron
    • Show all 30 messages in this topic