Re: Bug in Sun compiler WS6U2? - Crashes during compile phase with-fast.

From: Logan Shaw (lshaw-usenet_at_austin.rr.com)
Date: 03/24/05 

Date: Thu, 24 Mar 2005 01:20:57 GMT

Dave wrote:
> Logan Shaw wrote:
>> However, you can factor large
>> numbers that are the product of two primes, and if you did that, it'd
>> be a bad thing for cryptography as we know it.

> But it can factor a composite number consisting of two similar sized
> primes virtually instantly.
>
> In[10]:= 2760727302559 * 2760727302517 // multiple two primes.
>
> Out[10]= 7621615238978741781241003 // get the result
>
> In[11]:= FactorInteger[7621615238978741781241003] // factor it
>
> Out[11]= {{2760727302517, 1}, {2760727302559, 1}} // The two prime factors.

That Mathematica can do that nearly instantaneously is pretty impressive.

As far as I know, the only way to do this is to just brute force it
by dividing by numbers from 2 .. floor(sqrt(7621615238978741781241003))
until you get one that comes out evenly.

Actually, you can do a little better than that by using simple tests
to see if the number is a multiple of 2, 3, 5, etc. That allows you
to skip about 75% of the brute force divisions, but that only makes
your code something like 4 times as fast, which is not that much!

You still have to do something like 700 billion divisions to
find that, unless there is some optimization technique that I am
missing something.

Which actually there must be unless your copy of Mathematica is running
on some massively parallel computer with hundreds of ~1 GHz processors...

By the way, I think there are other methods of cryptography that
don't involve prime numbers, but I'm not aware of any methods of
public/private key cryptography that don't use prime numbers.
Not to say that they don't exist, but I'm not aware of them.

   - Logan

Relevant Pages

  • Re: Breaking LFSR.
    ... Everyone else has been very helpful - so far all your posts have been ... (primes are still primes, "E" is still the most common letter, etc). ... many bases is that the elements, representing numbers, are not ... Sci.crypt is entirely about computer cryptography. ...
    (sci.crypt)
  • Re: Breaking LFSR.
    ... presumption here that you are equating primes to pi status? ... Sci.crypt is entirely about computer cryptography. ... changing representations of numbers is cryptographically ...
    (sci.crypt)
  • Re: prime numbers?
    ... When talking about primes in reference to cryptography, ... are used when generating the public and private keys. ... Exclusive dedication to necessitious chores without interludes of ...
    (comp.security.misc)
  • Re: Bug in Sun compiler WS6U2? - Crashes during compile phase with-fast.
    ... >> Now if someone can find a fast way of factoring large prime numbers, ... I know you can't factor primes - by definition. ... course is that if there was found a way of factorising large composite ... it would be the end of cryptography. ...
    (comp.unix.solaris)
  • Re: finding primes
    ... find all primes between them. ... I basically wrote an initial function, bool isPrime, which ... loops over all numbers between 2 and sqrtto see if i%num == 0, ... force (all the mentioned solutions in this thread are brute force) for ...
    (comp.programming)