Re: factorization


Douglas A. Gwyn wrote:
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.

In fact, it can NOT lead to a P-time method. (unless P = NP)

Attempts to "reverse" the multiplication process by looking at the
digits leads to a system of diophantine equations whose solution
is known to be NPC. The basic problem is that one gets an
"exponential
explosion" of possible answers when analyzing the carries.

.

Relevant Pages

  • Re: factorization
    ... this fact can possibly lead to a factorization in polynomial time or ... and high-order digits ... factoring algorithm. ...
    (sci.crypt)
  • 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)
  • Prime Factorization and Digit Congruence
    ... of three digits as a decimal number. ... summation congruence for base b can be used as a test for the factor ... similar method for "a base that is a power of two". ... as I develop some factorization software. ...
    (sci.math)
  • Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting Dik ...)
    ... the known factorization of p-1 that you got when you directly ... Let n0 = random number with 80 digits, ...
    (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)