Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5682
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: really? (lame question about primes) |
| Date | 2015-09-01 11:01 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <ms3peh$o5v$1@dont-email.me> (permalink) |
| References | <5e5de47a-7353-4ffc-9f5d-ec083d1d63ba@googlegroups.com> <kt4Fx.394338$3n4.170027@fx35.am4> <44a165dc-8447-4ae0-8695-557a7ddf00cf@googlegroups.com> |
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.)
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web