Primes and Factorization

News:

  • April 2006: report on New Record Elliptic Curve (ECM) prime factor, 66-digits, titled 20 years of ECM, Zimmermann/Dodson accepted for presentation at ANTS VII (Algorithmic Number Theory Symposium, 7), Berlin, July 2006, proceedings in Springer Lecture Notes in CS.

    • Sieving, 1928-2003:

  • E. Tromer's presentation [abbreviated version]

    • Method of Trial Division is an exponential calculation

  • A favorite method from high school, if n is the product n = ab, with a smaller than b, then a 2 smaller than ab = n, and n has a prime factor smaller than the squareroot of n. So check the primes in order to find a factor of n; or else declare n to be a prime when the divisors reach the squareroot of n . Prime Count using the Prime Number Theorem.

  • Trial Division also suggests primality is harder than factoring. Both numerics and theory support the reverse; emphatically, in an easily visible way. Spring 2000 and Spring 2006.

    Methods: cryptographic numbers; small and medium prime factors

  • chronology
  • methods (ECM)

  • Lehigh ECMNET page ecmnet2004a; update ecmnet2004; update ecmnet2006.