Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5677 > unrolled thread
| Started by | fir <profesor.fir@gmail.com> |
|---|---|
| First post | 2015-08-31 12:07 -0700 |
| Last post | 2015-08-31 23:10 -0500 |
| Articles | 20 on this page of 53 — 11 participants |
Back to article view | Back to comp.programming
really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-08-31 12:07 -0700
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-08-31 23:23 +0100
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 01:18 -0700
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-01 11:01 +0200
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 12:20 +0100
Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-01 15:48 +0100
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:26 -0700
Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:12 -0500
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 08:38 +0100
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:03 +0200
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:24 -0700
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 22:27 +0100
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 15:02 -0700
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 23:20 +0100
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:22 +0200
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 17:18 -0700
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:19 +0100
Re: really? (lame question about primes) James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-02 12:42 +0000
Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 14:21 +0100
Re: really? (lame question about primes) Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-02 17:45 +0200
Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 18:06 +0100
Re: really? (lame question about primes) James Dow Allen <jdallen2000@yahoo.com> - 2015-09-03 17:05 -0700
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-04 02:18 +0200
Re: really? (lame question about primes) Chad <cdalten@gmail.com> - 2015-09-03 22:37 -0700
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-03 23:49 -0700
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-04 00:18 -0700
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-04 08:25 +0100
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 14:36 +0100
Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 16:49 +0100
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 17:32 +0100
Re: really? (lame question about primes) Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 22:55 +0000
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:15 +0200
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 03:19 +0200
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:37 +0100
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 11:24 +0200
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 10:42 +0100
Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-02 03:01 -0700
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 12:28 +0200
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:12 +0200
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:19 +0100
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 14:56 +0200
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 15:47 +0200
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 16:27 +0200
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 16:37 +0200
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 17:01 +0200
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 10:55 +0200
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:05 +0100
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 11:49 +0200
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:54 +0100
Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 13:22 +0200
Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-03 13:58 +0200
Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:34 +0100
Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-08-31 23:10 -0500
Page 1 of 3 [1] 2 3 Next page →
| From | fir <profesor.fir@gmail.com> |
|---|---|
| Date | 2015-08-31 12:07 -0700 |
| Subject | really? (lame question about primes) |
| Message-ID | <5e5de47a-7353-4ffc-9f5d-ec083d1d63ba@googlegroups.com> |
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
[toc] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-08-31 23:23 +0100 |
| Message-ID | <kt4Fx.394338$3n4.170027@fx35.am4> |
| In reply to | #5677 |
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
[toc] | [prev] | [next] | [standalone]
| From | fir <profesor.fir@gmail.com> |
|---|---|
| Date | 2015-09-01 01:18 -0700 |
| Message-ID | <44a165dc-8447-4ae0-8695-557a7ddf00cf@googlegroups.com> |
| In reply to | #5678 |
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)
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2015-09-01 11:01 +0200 |
| Message-ID | <ms3peh$o5v$1@dont-email.me> |
| In reply to | #5681 |
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.)
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-09-01 12:20 +0100 |
| Message-ID | <_RfFx.418341$bt.398932@fx32.am4> |
| In reply to | #5682 |
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
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-09-01 15:48 +0100 |
| Message-ID | <87y4gqmc0c.fsf@bsb.me.uk> |
| In reply to | #5684 |
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.
[toc] | [prev] | [next] | [standalone]
| From | fir <profesor.fir@gmail.com> |
|---|---|
| Date | 2015-09-01 13:26 -0700 |
| Message-ID | <72950765-94b6-453f-8271-bce769c9ea28@googlegroups.com> |
| In reply to | #5686 |
W dniu wtorek, 1 września 2015 16:48:23 UTC+2 użytkownik Ben Bacarisse napisał: > 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)
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2015-09-02 02:12 -0500 |
| Message-ID | <v67dua9hl4qonlcajvo5j4ftpbk9c69g0p@4ax.com> |
| In reply to | #5691 |
On Tue, 1 Sep 2015 13:26:50 -0700 (PDT), fir <profesor.fir@gmail.com> wrote: >W dniu wtorek, 1 wrze?nia 2015 16:48:23 UTC+2 u?ytkownik Ben Bacarisse napisa?: >> 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) Generating large primes is fairly easy, especially, as is almost always the case, you're willing to accept a probabilistic primality test. If you want, for example a 1024 bit prime, output a 1, 1022 random bits, and another 1. That generates a 1024 bit, odd, random number. Test if it's prime. If so, great, you're done. Otherwise, add 2 (obviously there's no need to test even numbers), and test again. Repeat as needed. In the vicinity of 2**1024, about one in 700 numbers is prime, so the average number of iterations for the above is ~175, before finding a prime. The probabilistic primality tests return some probability of the number being prime or composite, and you can run them multiple times to generate any probability you want. For example, one iteration Miller-Rabin will return "composite" 75% of the time if the number is non-prime. Apply 50 iterations of that and the odds of accepting a composite number as prime is about 1 in 2**100. Incidentally 75% is a worst case, in almost all cases the odds of Miller-Rabin missing a composite is vastly smaller. OTOH, a few (or a bunch) of extra rounds of Miller-Rabin aren't usually expensive enough to avoid, especially as you're going to be discarding a fair number of candidate numbers anyway (in this example, you'll be looking at an average of ~175 numbers before finding a prime, and each of those will usually be discarded with a single round of Miller-Rabin - adding an extra 49 rounds to verify the final number only increases the total work by a quarter. If you want a deterministic test, those are (in practice) too slow (except for special cases), but still massively faster than the factoring problem. https://en.wikipedia.org/wiki/Primality_test
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-09-02 08:38 +0100 |
| Message-ID | <eIxFx.410097$GZ.317970@fx21.am4> |
| In reply to | #5702 |
On 02/09/2015 08:12, Robert Wessel wrote: <snip> > The probabilistic primality tests return some probability of the > number being prime or composite, and you can run them multiple times > to generate any probability you want. For example, one iteration > Miller-Rabin will return "composite" 75% of the time if the number is > non-prime. Apply 50 iterations of that and the odds of accepting a > composite number as prime is about 1 in 2**100. Rubbish! It's *exactly* 1 in 2**100. :-) Putting it another way, you are: 99.999999999999999999999999999921% likely to get a prime. I only use 20 iterations, so I have 1 in 2**40 chance of getting a composite by mistake, which means I'm only 99.9999999999% likely to get a prime. 2**40 is 1099511627776. For comparison, my chance of winning the UK National Lottery is roughly 1 in 14000000 - I am, therefore, over 75,000 times as likely to win the Lottery* as I am to get a composite number by mistake. *Or would be, if I ever bought a ticket. -- 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
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2015-09-02 14:03 +0200 |
| Message-ID | <ms6oer$ctv$1@dont-email.me> |
| In reply to | #5704 |
On 02/09/15 09:38, Richard Heathfield wrote: > On 02/09/2015 08:12, Robert Wessel wrote: > > <snip> > >> The probabilistic primality tests return some probability of the >> number being prime or composite, and you can run them multiple times >> to generate any probability you want. For example, one iteration >> Miller-Rabin will return "composite" 75% of the time if the number is >> non-prime. Apply 50 iterations of that and the odds of accepting a >> composite number as prime is about 1 in 2**100. > > Rubbish! It's *exactly* 1 in 2**100. :-) > > Putting it another way, you are: > > 99.999999999999999999999999999921% likely to get a prime. > > I only use 20 iterations, so I have 1 in 2**40 chance of getting a > composite by mistake, which means I'm only 99.9999999999% likely to get > a prime. > > 2**40 is 1099511627776. For comparison, my chance of winning the UK > National Lottery is roughly 1 in 14000000 - I am, therefore, over 75,000 > times as likely to win the Lottery* as I am to get a composite number by > mistake. Just make sure you don't do 19.93 iterations - as we know, 1 in a million chances crop up 9 times out of 10. > > *Or would be, if I ever bought a ticket. > I got a letter the other day telling me I had one the European Lottery, even though I had not bought a ticket - all I had to do was send them my bank details and my mother's maiden name so that they could transfer the winnings.
[toc] | [prev] | [next] | [standalone]
| From | fir <profesor.fir@gmail.com> |
|---|---|
| Date | 2015-09-01 13:24 -0700 |
| Message-ID | <d91bce8a-2655-4db6-8fc3-ce1df53e959b@googlegroups.com> |
| In reply to | #5684 |
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
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-09-01 22:27 +0100 |
| Message-ID | <uLoFx.516161$Me5.63982@fx42.am4> |
| In reply to | #5690 |
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
[toc] | [prev] | [next] | [standalone]
| From | fir <profesor.fir@gmail.com> |
|---|---|
| Date | 2015-09-01 15:02 -0700 |
| Message-ID | <5954b4ea-b6af-4216-a288-66301d20c67a@googlegroups.com> |
| In reply to | #5692 |
W dniu wtorek, 1 września 2015 23:27:58 UTC+2 użytkownik Richard Heathfield napisał: > 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? > 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)
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-09-01 23:20 +0100 |
| Message-ID | <4xpFx.791070$sY7.495062@fx30.am4> |
| In reply to | #5693 |
On 01/09/2015 23:02, fir wrote: > W dniu wtorek, 1 września 2015 23:27:58 UTC+2 użytkownik Richard Heathfield napisał: <snip> >> >> 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 Then perhaps you should be even more abusive - when *nobody* answers you, that will be even more pleasant for 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
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartek@gmail.com> |
|---|---|
| Date | 2015-09-02 01:22 +0200 |
| Message-ID | <ms5bvc$n5n$2@speranza.aioe.org> |
| In reply to | #5694 |
On 02.09.2015 00:20, Richard Heathfield wrote: > On 01/09/2015 23:02, fir wrote: >> W dniu wtorek, 1 września 2015 23:27:58 UTC+2 użytkownik Richard >> Heathfield napisał: > > <snip> > >>> >>> 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 > > Then perhaps you should be even more abusive - when *nobody* answers > you, that will be even more pleasant for you. No, no, please, keep him! ;) best regards from pl.comp.programming bartekltg
[toc] | [prev] | [next] | [standalone]
| From | fir <profesor.fir@gmail.com> |
|---|---|
| Date | 2015-09-01 17:18 -0700 |
| Message-ID | <9991fe20-bfea-48e1-9c44-3e4ca2f822e7@googlegroups.com> |
| In reply to | #5697 |
W dniu środa, 2 września 2015 01:22:23 UTC+2 użytkownik bartekltg napisał: > On 02.09.2015 00:20, Richard Heathfield wrote: > > On 01/09/2015 23:02, fir wrote: > >> W dniu wtorek, 1 września 2015 23:27:58 UTC+2 użytkownik Richard > >> Heathfield napisał: > > > > <snip> > > > >>> > >>> 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 > > > > Then perhaps you should be even more abusive - when *nobody* answers > > you, that will be even more pleasant for you. > > No, no, please, keep him! > ;) > > best regards from pl.comp.programming > bartekltg yea right now i cannot free myself from two blablers paradoxivcally they worry that if they 'abandon me' i will be alone in the whole usenet maybe even internet fun guys but not really.. let them also allow resolve C=A*B where C and A are known and fixed by "10^300 multiplies";C
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-09-02 02:19 +0100 |
| Message-ID | <d8sFx.324164$tz.265438@fx02.am4> |
| In reply to | #5698 |
On 02/09/2015 01:18, fir wrote: > let them also allow resolve C=A*B > where C and A are known and fixed > by "10^300 multiplies";C If C and A are known, then B is trivial to calculate. But if C is the only known, then A and B are rather harder to find. Here's a product of two primes: 58240024563391777851261291575917006595873586378340\ 06933501482037788347032155265963843106235363953614\ 49841148805852200248028532053742301130515851591046\ 09780764992214765245952615895162196506824080887010\ 84909798795532569027855897144990861217719976822376\ 60245183108382607111271438893289345453397044868767\ 74937653432105197140786655752847106640293149009133\ 49133637852917819933171853595092059610555346845194\ 20546782513079321228879093216436059864014065839170\ 63336369425428124884924467183572745778186732426767\ 31177226131629502125332694404335922836373000524949\ 96264733742856842752930777926209786527196791359153\ 71 (Backslash used as a line continuation character.) Good luck factoring it. -- 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
[toc] | [prev] | [next] | [standalone]
| From | James Dow Allen <gmail@jamesdowallen.nospam> |
|---|---|
| Date | 2015-09-02 12:42 +0000 |
| Message-ID | <XnsA509C8731C226jamesdowallen@178.63.61.175> |
| In reply to | #5699 |
Richard Heathfield <rjh@cpax.org.uk> might have writ, in news:d8sFx.324164 $tz.265438@fx02.am4: > Here's a product of two primes: > > 58240024563391777851261291575917006595873586378340\ > 06933501482037788347032155265963843106235363953614\ > 49841148805852200248028532053742301130515851591046\ > 09780764992214765245952615895162196506824080887010\ > 84909798795532569027855897144990861217719976822376\ > 60245183108382607111271438893289345453397044868767\ > 74937653432105197140786655752847106640293149009133\ > 49133637852917819933171853595092059610555346845194\ > 20546782513079321228879093216436059864014065839170\ > 63336369425428124884924467183572745778186732426767\ > 31177226131629502125332694404335922836373000524949\ > 96264733742856842752930777926209786527196791359153\ > 71 > > Good luck factoring it. Now you're just being sadistic. (And BTW how did you come up with that number?) I'll be impressed by whoever is first to factor this number 6666666666666666666666666666666664295863450544367679162527001239842359 (Please tell us how you did it.) James
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-09-02 14:21 +0100 |
| Message-ID | <87twrdhs7w.fsf@bsb.me.uk> |
| In reply to | #5715 |
James Dow Allen <gmail@jamesdowallen.nospam> writes: > Richard Heathfield <rjh@cpax.org.uk> might have writ, in news:d8sFx.324164 > $tz.265438@fx02.am4: > >> Here's a product of two primes: >> >> 58240024563391777851261291575917006595873586378340\ >> 06933501482037788347032155265963843106235363953614\ >> 49841148805852200248028532053742301130515851591046\ >> 09780764992214765245952615895162196506824080887010\ >> 84909798795532569027855897144990861217719976822376\ >> 60245183108382607111271438893289345453397044868767\ >> 74937653432105197140786655752847106640293149009133\ >> 49133637852917819933171853595092059610555346845194\ >> 20546782513079321228879093216436059864014065839170\ >> 63336369425428124884924467183572745778186732426767\ >> 31177226131629502125332694404335922836373000524949\ >> 96264733742856842752930777926209786527196791359153\ >> 71 >> >> Good luck factoring it. > > Now you're just being sadistic. (And BTW how did you come up with that > number?) > > I'll be impressed by whoever is first to factor this number > 6666666666666666666666666666666664295863450544367679162527001239842359 = 67499999992406250000094921874999003 x 98765432109876543210987654321098453 > (Please tell us how you did it.) Too embarrassed! -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Johannes Bauer <dfnsonfsduifb@gmx.de> |
|---|---|
| Date | 2015-09-02 17:45 +0200 |
| Message-ID | <ms75i6$i19$1@news.albasani.net> |
| In reply to | #5718 |
On 02.09.2015 15:21, Ben Bacarisse wrote: >> (Please tell us how you did it.) > > Too embarrassed! sage: print(factor(6666666666666666666666666666666664295863450544367679162527001239842359 )) 67499999992406250000094921874999003 * 98765432109876543210987654321098453 Took just over 2 minutes on my system. Was that how you did it? Cheers, Johannes -- >> Wo hattest Du das Beben nochmal GENAU vorhergesagt? > Zumindest nicht öffentlich! Ah, der neueste und bis heute genialste Streich unsere großen Kosmologen: Die Geheim-Vorhersage. - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1@speranza.aioe.org>
[toc] | [prev] | [next] | [standalone]
Page 1 of 3 [1] 2 3 Next page →
Back to top | Article view | comp.programming
csiph-web