Re: Prime Decomposition

From: Carlos Moreno (moreno_at_mochima_dot_com_at_xx.xxx)
Date: 10/19/04 

Date: Tue, 19 Oct 2004 17:37:54 -0400

Charles Milutinovic wrote:
> Hello all. I know there is a stupidly simple algorithm for prime
> decomposition (besides the naieve one of testing all primes from 2 until
> exhaustion) but my memory and google is failing me. This is going to be
> part of a program that uses a modified version of the el-gammel encryption
> algorithm, and hense we are dealing with primes around 2^1024 to 2^2048 i.e.
> large enough that the naieve algorithm is (probably) too slow. Can someone
> please point me in the right direction?

I'm surprised that a person that knows about these encryption
techniques doesn't know the most widely-known and obvious
fact in the world of cryptography: Factoring large numbers
in a reasonable amount of time is a problem for which there
is no publicly known solution (i.e., known to the scientific
community).

The security of many cryptographic techniques (such as the
RSA public-key cryptosystem) relies on the "impossibility"
of factoring large numbers in a reasonable amount of time.

That means that whatever you're trying to do, if it really
*requires* that you factor numbers with prime factorization
consisting of prime numbers in the range of 2^512 or more,
then what you're trying to do can not be done. There is no
guarantee about whether or not it will be possible tomorrow,
or some time in the near future (though it is believed that
it still won't be possible).

HTH,

Carlos 

--

Relevant Pages

  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)
  • Re: More math stuff, truth and social reality
    ... > out that I use brainstorming, where you generate lots of ideas during ... fast as other efficient factoring algorithms. ... I don't see evidence of lying, ... algorithm) is in fact the truth. ...
    (sci.math)