Re: factorization

Mirror wrote:
All prime numbers - except 2 and 5 - have as their last digit, either
1 or 3 or 7 or 9.

Duh.

We notice that the last digit of the multiplication of two prime
numbers is also 1,3,7 or 9. How is that ?

False: 5 * 7 = 35, last digit is 5
2 * 3 = 6, last digit is 6

...
this fact can possibly lead to a factorization in polynomial time or
even faster.

Many people have tried a more sophisticated analysis of the low-
and high-order digits (usually bits, rather than decimal digits)
but haven't yet been able to turn the idea into a practical
factoring algorithm.
.

Relevant Pages

  • Re: Consecutive Numbers
    ... NP problem is said to be NP-complete if the>existence of a polynomial ... footing--- if any one of them can be solved in polynomial time, ... to be non-P or NP>"Finding the prime factors of a given integer is ... it does, then factorization, which is certainly in NP ...
    (sci.math)
  • Re: JSH: Easy math, easy solution
    ... >website and do their prime factorization challenge. ... All of these steps can be performed in polynomial time on a classical ... time using both a quantum computer and a classical computer. ...
    (sci.math)
  • Re: Basically a sieve method, relation to quantum
    ... > factorization of 2*M, but your idea is much simpler and more elegant. ... and yours is just the special case of picking j=M (I know James ... be factored in polynomial time if he got to assume instead that factoring ... even I can write a linear-time Python program ...
    (sci.crypt)
  • If P==NP how to solve the Prime Factorization problem?
    ... I am looking for information on "if a polynomial time algorithm exists ... factorization ends up in P. ... for any other NP-Complete problem. ...
    (comp.theory)
  • Re: Basically a sieve method, relation to quantum
    ... > factorization of 2*M, but your idea is much simpler and more elegant. ... and yours is just the special case of picking j=M (I know James ... be factored in polynomial time if he got to assume instead that factoring ... even I can write a linear-time Python program ...
    (sci.math)