[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

really? (lame question about primes

kenobi

8/31/2015 7:08:00 PM

I heard (read some) thet if one will take two large primes A, B (like 300 digits or so) and multiply them to C (will probably get 600 digit number) - then will gave some task to de-factorise C on A and B then it is today impossible task - used in cryptography

really it is so hard? maybe it is but isnt then a proces of finding those 300-digit primes also hard? is it possible to find A and B (which need much more test as all factors must be checked) but this is harder to make a lot of simple multiplies scanning
some propositions? (as C lenght is given
for given a some B could be like deduced - or instead of checking many A*B only divisions C/A == B could be checked..

whats with that
52 Answers

Richard Heathfield

8/31/2015 10:23:00 PM

0

On 31/08/2015 20:07, fir wrote:
> I heard (read some) thet if one will take two large primes A, B (like 300 digits or so) and multiply them to C (will probably get 600 digit number) - then will gave some task to de-factorise C on A and B then it is today impossible task - used in cryptography

A few years ago, it was announced that a 232-digit integer had been
factored. It had taken two years, using hundreds of computers working
together. To factor a 600-digit integer would take many times the
lifetime of the universe, given the current state of the art.

> really it is so hard?

The best information we have at present is that yes, it really is so
hard. That does not mean that someone might discover a neat mathematical
trick tomorrow that will make it easy. (Nor does it mean that an easy
way has not been found privately.) But our best guess right now is that
it's really, really, really hard.

> maybe it is but isnt then a proces of finding those 300-digit primes also hard?

Nothing like /as/ hard, no. I can easily generate primes of 300 digits
or more, very very quickly, and multiply them even more quickly.

> is it possible to find A and B (which need much more test as all
factors must be checked) but this is harder to make a lot of simple
multiplies scanning
> some propositions?

Generating primes is easier than you make it sound, especially if you
are prepared to accept probable primes (integers that have a probability
of, say, 99.99999999999% of being prime), because there are mathematical
short-cuts we can use (e.g. Rabin-Miller). There is no publicly-known
mathematical short-cut that makes factoring easy, though. (Some
short-cuts exist, but they don't make it easy - they just make it not
quite as hard.) It may be that someone has come up with a method and is
keeping it a secret but, by definition, we don't know that either way.


> (as C lenght is given
> for given a some B could be like deduced - or instead of checking many A*B only divisions C/A == B could be checked..

Division is actually more expensive than multiplication, so this doesn't
help.

> whats with that

It's just a fact of life that there are some problems that are (as far
as is currently known) not solvable other than by very time-consuming
techniques.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

robertwessel2@yahoo.com

9/1/2015 4:10:00 AM

0

On Mon, 31 Aug 2015 12:07:52 -0700 (PDT), fir <profesor.fir@gmail.com>
wrote:

>I heard (read some) thet if one will take two large primes A, B (like 300 digits or so) and multiply them to C (will probably get 600 digit number) - then will gave some task to de-factorise C on A and B then it is today impossible task - used in cryptography
>
>really it is so hard? maybe it is but isnt then a proces of finding those 300-digit primes also hard? is it possible to find A and B (which need much more test as all factors must be checked) but this is harder to make a lot of simple multiplies scanning
>some propositions? (as C lenght is given
>for given a some B could be like deduced - or instead of checking many A*B only divisions C/A == B could be checked..
>
>whats with that


A good place to start reading:

https://en.wikipedia.org/wiki/Integer_fac...

kenobi

9/1/2015 8:18:00 AM

0

W dniu wtorek, 1 wrzesnia 2015 00:23:16 UTC+2 uzytkownik Richard Heathfield napisal:
> On 31/08/2015 20:07, fir wrote:
> > I heard (read some) thet if one will take two large primes A, B (like 300 digits or so) and multiply them to C (will probably get 600 digit number) - then will gave some task to de-factorise C on A and B then it is today impossible task - used in cryptography
>
> A few years ago, it was announced that a 232-digit integer had been
> factored. It had taken two years, using hundreds of computers working
> together. To factor a 600-digit integer would take many times the
> lifetime of the universe, given the current state of the art.
>
> > really it is so hard?
>
> The best information we have at present is that yes, it really is so
> hard. That does not mean that someone might discover a neat mathematical
> trick tomorrow that will make it easy. (Nor does it mean that an easy
> way has not been found privately.) But our best guess right now is that
> it's really, really, really hard.
>
> > maybe it is but isnt then a proces of finding those 300-digit primes also hard?
>
> Nothing like /as/ hard, no. I can easily generate primes of 300 digits
> or more, very very quickly, and multiply them even more quickly.
>
> > is it possible to find A and B (which need much more test as all
> factors must be checked) but this is harder to make a lot of simple
> multiplies scanning
> > some propositions?
>
> Generating primes is easier than you make it sound, especially if you
> are prepared to accept probable primes (integers that have a probability
> of, say, 99.99999999999% of being prime), because there are mathematical
> short-cuts we can use (e.g. Rabin-Miller). There is no publicly-known
> mathematical short-cut that makes factoring easy, though. (Some
> short-cuts exist, but they don't make it easy - they just make it not
> quite as hard.) It may be that someone has come up with a method and is
> keeping it a secret but, by definition, we don't know that either way.
>
>
> > (as C lenght is given
> > for given a some B could be like deduced - or instead of checking many A*B only divisions C/A == B could be checked..
>
> Division is actually more expensive than multiplication, so this doesn't
> help.
>
> > whats with that
>
> It's just a fact of life that there are some problems that are (as far
> as is currently known) not solvable other than by very time-consuming
> techniques.
>

but if generating primes is cheap you could maybe not try to factorise C
(which may be hard i may belive)
but generate mass number of primes
multiply them tl find C 9esp as this seem one dimensional task or nearly in scanning
thru A as B is given probably from equation log(A*B) = log(A)+log(B)
thus log(B) = log(C)-log(A) so for given A
B = exp(log(C)-log(A))

it would be somewhat realli interesting
to wrote such bignum routines myself
once to check how costly this all is (and what various institutions use to quickly count such things [should move it to c if so as this is c routines topic here)

David Brown

9/1/2015 9:02:00 AM

0

On 01/09/15 10:18, fir wrote:
> W dniu wtorek, 1 wrzeÅ?nia 2015 00:23:16 UTC+2 użytkownik Richard Heathfield napisaÅ?:
>> On 31/08/2015 20:07, fir wrote:
>>> I heard (read some) thet if one will take two large primes A, B (like 300 digits or so) and multiply them to C (will probably get 600 digit number) - then will gave some task to de-factorise C on A and B then it is today impossible task - used in cryptography
>>
>> A few years ago, it was announced that a 232-digit integer had been
>> factored. It had taken two years, using hundreds of computers working
>> together. To factor a 600-digit integer would take many times the
>> lifetime of the universe, given the current state of the art.
>>
>>> really it is so hard?
>>
>> The best information we have at present is that yes, it really is so
>> hard. That does not mean that someone might discover a neat mathematical
>> trick tomorrow that will make it easy. (Nor does it mean that an easy
>> way has not been found privately.) But our best guess right now is that
>> it's really, really, really hard.
>>
>>> maybe it is but isnt then a proces of finding those 300-digit primes also hard?
>>
>> Nothing like /as/ hard, no. I can easily generate primes of 300 digits
>> or more, very very quickly, and multiply them even more quickly.
>>
>>> is it possible to find A and B (which need much more test as all
>> factors must be checked) but this is harder to make a lot of simple
>> multiplies scanning
>>> some propositions?
>>
>> Generating primes is easier than you make it sound, especially if you
>> are prepared to accept probable primes (integers that have a probability
>> of, say, 99.99999999999% of being prime), because there are mathematical
>> short-cuts we can use (e.g. Rabin-Miller). There is no publicly-known
>> mathematical short-cut that makes factoring easy, though. (Some
>> short-cuts exist, but they don't make it easy - they just make it not
>> quite as hard.) It may be that someone has come up with a method and is
>> keeping it a secret but, by definition, we don't know that either way.
>>
>>
>>> (as C lenght is given
>>> for given a some B could be like deduced - or instead of checking many A*B only divisions C/A == B could be checked..
>>
>> Division is actually more expensive than multiplication, so this doesn't
>> help.
>>
>>> whats with that
>>
>> It's just a fact of life that there are some problems that are (as far
>> as is currently known) not solvable other than by very time-consuming
>> techniques.
>>
>
> but if generating primes is cheap you could maybe not try to factorise C
> (which may be hard i may belive)
> but generate mass number of primes
> multiply them tl find C 9esp as this seem one dimensional task or nearly in scanning
> thru A as B is given probably from equation log(A*B) = log(A)+log(B)
> thus log(B) = log(C)-log(A) so for given A
> B = exp(log(C)-log(A))
>
> it would be somewhat realli interesting
> to wrote such bignum routines myself
> once to check how costly this all is (and what various institutions use to quickly count such things [should move it to c if so as this is c routines topic here)
>

Yes, you can factorise C by trying to multiply pairs A * B and see if
they match. The trouble is, with a 600 digit number there are quite a
lot of such pairs to try!

(Using log/exp instead of multiplying or dividing is not helpful here -
you need to have absolute accuracy on your integers, and this leads to
enormous accuracy requirements on your log/exp calculations. log/exp
tricks are great for rough estimates, but not for precise calculations.)

Richard Heathfield

9/1/2015 11:20:00 AM

0

On 01/09/2015 10:01, David Brown wrote:

<snip>

> Yes, you can factorise C by trying to multiply pairs A * B and see if
> they match. The trouble is, with a 600 digit number there are quite a
> lot of such pairs to try!

Well, there aren't all that many really, and the OP specified two
300-digit integers, so we needn't bother with lower numbers.

There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
= 8.1*10^599 pairs.

Let's further assume that we have a million million (10^12) computers at
our disposal, and that each of these is capable of multiplying a million
million pairs a second. So we can test 10^24 pairs per second, which
means we will definitely find the result within 8.1*10^575 seconds.
Assuming average luck, call that 4*10^575 seconds. This turns out to be
1.267*10^468 as long as it takes for the universe to die of entropy.

Looking at it the other way, if we assume average luck and want the
result within, say, a million seconds (11.5 days):

4*10^575 / 1000000 = 4*10^569

Square root of 4*10^569 is roughly 6.3*10^284.

So instead of a million million computers working at a million million
pairs per second, we need

630,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
computers each capable of multiplying

630,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
pairs of 300-digit integers per second.

Power crisis? What power crisis?

<snip>

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Ben Bacarisse

9/1/2015 2:48:00 PM

0

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 01/09/2015 10:01, David Brown wrote:
>
> <snip>
>
>> Yes, you can factorise C by trying to multiply pairs A * B and see if
>> they match. The trouble is, with a 600 digit number there are quite a
>> lot of such pairs to try!
>
> Well, there aren't all that many really, and the OP specified two
> 300-digit integers, so we needn't bother with lower numbers.
>
> There are only 9*10^299 300-digit numbers, so we need to test
> 81*10^598 = 8.1*10^599 pairs.

Although that's not fir's suggested algorithm. He suggests testing only
primes as divisors and he might think that large primes are "rare" (many
people do).

The prime number theorem gives a lower bound (for x > 10) of x/log(x)
for the number of primes less than x, so it's not hard to see that
testing prime divisors alone won't help the calculations very much (and
may make matters worse by having to make them in the first place).

(Yes, I know you were mainly being humorous, but if someone thinks that
there are very few large primes the joke would be pointless.)

<snip>
--
Ben.

kenobi

9/1/2015 8:24:00 PM

0

W dniu wtorek, 1 wrzesnia 2015 13:20:29 UTC+2 uzytkownik Richard Heathfield napisal:
> On 01/09/2015 10:01, David Brown wrote:
>
> <snip>
>
> > Yes, you can factorise C by trying to multiply pairs A * B and see if
> > they match. The trouble is, with a 600 digit number there are quite a
> > lot of such pairs to try!
>
> Well, there aren't all that many really, and the OP specified two
> 300-digit integers, so we needn't bother with lower numbers.
>
> There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
> = 8.1*10^599 pairs.
>
preposterous bullshit - i said that A length is strictly related to B length

kenobi

9/1/2015 8:27:00 PM

0

W dniu wtorek, 1 wrzesnia 2015 16:48:23 UTC+2 uzytkownik Ben Bacarisse napisal:
> Richard Heathfield <rjh@cpax.org.uk> writes:
>
> > On 01/09/2015 10:01, David Brown wrote:
> >
> > <snip>
> >
> >> Yes, you can factorise C by trying to multiply pairs A * B and see if
> >> they match. The trouble is, with a 600 digit number there are quite a
> >> lot of such pairs to try!
> >
> > Well, there aren't all that many really, and the OP specified two
> > 300-digit integers, so we needn't bother with lower numbers.
> >
> > There are only 9*10^299 300-digit numbers, so we need to test
> > 81*10^598 = 8.1*10^599 pairs.
>
> Although that's not fir's suggested algorithm. He suggests testing only
> primes as divisors and he might think that large primes are "rare" (many
> people do).
>
> The prime number theorem gives a lower bound (for x > 10) of x/log(x)
> for the number of primes less than x, so it's not hard to see that
> testing prime divisors alone won't help the calculations very much (and
> may make matters worse by having to make them in the first place).
>
> (Yes, I know you were mainly being humorous, but if someone thinks that
> there are very few large primes the joke would be pointless.)
>
well not necessary small amount of primes but maybe small amount of known primes (i thought that maybe finding them is harder,
and one who code c must first know A and B)

Richard Heathfield

9/1/2015 9:28:00 PM

0

On 01/09/2015 21:24, fir wrote:
> W dniu wtorek, 1 wrzeÅ?nia 2015 13:20:29 UTC+2 użytkownik Richard Heathfield napisaÅ?:
>> On 01/09/2015 10:01, David Brown wrote:
>>
>> <snip>
>>
>> > Yes, you can factorise C by trying to multiply pairs A * B and see if
>> > they match. The trouble is, with a 600 digit number there are quite a
>> > lot of such pairs to try!
>>
>> Well, there aren't all that many really, and the OP specified two
>> 300-digit integers, so we needn't bother with lower numbers.
>>
>> There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
>> = 8.1*10^599 pairs.
>>
> preposterous bullshit - i said that A length is strictly related to B length

If you will take the trouble to read what I wrote a little more
carefully, you will see that I had A's and B's length exactly equal (300
(decimal) digits). How is "exactly equal" not strictly related?

Because in your original question you took a little care to be lucid, I
answered your question, politely and reasonably thoroughly, despite the
fact that you have been less than polite in previous exchanges between us.

Your response to my polite and reasonably thorough answer is not only
incorrect, but also vehemently abusive.

Is it any wonder, then, that fewer and fewer people are responding to you?

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

kenobi

9/1/2015 10:02:00 PM

0

W dniu wtorek, 1 wrzesnia 2015 23:27:58 UTC+2 uzytkownik Richard Heathfield napisal:
> On 01/09/2015 21:24, fir wrote:
> > W dniu wtorek, 1 wrzesnia 2015 13:20:29 UTC+2 uzytkownik Richard Heathfield napisal:
> >> On 01/09/2015 10:01, David Brown wrote:
> >>
> >> <snip>
> >>
> >> > Yes, you can factorise C by trying to multiply pairs A * B and see if
> >> > they match. The trouble is, with a 600 digit number there are quite a
> >> > lot of such pairs to try!
> >>
> >> Well, there aren't all that many really, and the OP specified two
> >> 300-digit integers, so we needn't bother with lower numbers.
> >>
> >> There are only 9*10^299 300-digit numbers, so we need to test 81*10^598
> >> = 8.1*10^599 pairs.
> >>
> > preposterous bullshit - i said that A length is strictly related to B length
>
> If you will take the trouble to read what I wrote a little more
> carefully, you will see that I had A's and B's length exactly equal (300
> (decimal) digits). How is "exactly equal" not strictly related?
>
> Because in your original question you took a little care to be lucid, I
> answered your question, politely and reasonably thoroughly, despite the
> fact that you have been less than polite in previous exchanges between us.
>
> Your response to my polite and reasonably thorough answer is not only
> incorrect, but also vehemently abusive.
>
> Is it any wonder, then, that fewer and fewer people are responding to you?
>
It is not a wonder it is very pleasant - would be as such simpletons as you and brown still try to stick to ma wasting my time - and that is a trouble you know how to resolve - stay away and give a gift of your level of intelligence (which is kinda of depressing and boring fun ) to your own 'collegues' ;C - coz there is no other option a level of your low intelligence is uterrly incompatible with my own - and it will not change it may be even worse (and take a db preposterous cheater with ya;C)