Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5785
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: really? (lame question about primes) |
| Date | 2015-09-03 10:55 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <ms91q8$d83$1@dont-email.me> (permalink) |
| References | (11 earlier) <ms6rm0$td4$1@speranza.aioe.org> <ms6uia$57r$1@dont-email.me> <ms710a$beb$1@speranza.aioe.org> <ms71gl$hho$1@dont-email.me> <ms7300$gk6$1@speranza.aioe.org> |
On 02/09/15 17:01, bartekltg wrote: > On 02.09.2015 16:37, David Brown wrote: >> On 02/09/15 16:27, bartekltg wrote: >>> On 02.09.2015 15:47, David Brown wrote: >>>> On 02/09/15 14:56, bartekltg wrote: >>>>> On 02.09.2015 14:19, Richard Heathfield wrote: >>>>>> On 02/09/2015 13:12, David Brown wrote: >>>>>>> >>>>>> <snip> >>>>>>> >>>>>>> There are a number of ways of doing this check faster than the >>>>>>> bit-for-bit long division you suggested elsewhere, >>>>>> >>>>>> The advantage of that way is that it's easy to explain, and >>>>>> relatively >>>>>> easy to implement. Having said that, I *haven't* implemented it (in >>>>>> software). My bignum library uses Algorithm D, from TAOCP II. >>>>> >>>>> I think explain something by using wrong algorithm can hurt >>>>> someone who think, so propably everyone who is listening to >>>>> 'how to factorize an integer;-)' >>>>> >>>>> But we can resurect this idea. >>>>> >>>>> Table of all n-digits prime can be too big for the universe, >>>>> so we have to generate it. One ot the simplest method is >>>>> to implement 'nextprime' - function that get the next odd*) >>>>> number and run fast primality test (Miller-Rabin), >>>>> repeat it until the number is pseudoprime. >>>>> >>>> >>>> The principle here is that to find the factors of C, we run through all >>>> primes A up to sqrt(C), and test if C % A == 0. (It may be that there >>>> are other faster algorithms, but I don't know of any.) If you know for >>>> sure the number of digits in A, then you could start 10^(noOfDigits-1), >>>> but that would only save 10% of the test time. >>>> >>>> Testing for the primality of each A is going to take a great deal more >>>> time than simply trying C % A == 0, even with a probable prime >>>> test. It >>>> is simply not worth doing. >>>> >>>> What would be worth doing, I think, is to keep a track of A % p for >>>> p in >>>> the first n primes. As you run through the A's, adding 2 to A each >>>> step, you add 2 to each of these remainders in your tracking array. If >>>> these hit 0 (modulo their prime), then A is clearly non-prime and you >>>> can skip it. This will let you skip a number of your test divisions >>>> with relatively little work - as you make that array of n primes >>>> bigger, >>>> you cut out yet more divisions. However, there is going to be a point >>>> where doing this tracking for the modulo A % p will cost more (in >>>> memory >>>> or speed) than 1/p times the cost of calculating C % A - and when you >>>> reach that, you don't want to track any more modulos. >>>> >>>> I suspect there is scope for some interesting data structures to hold >>>> this list of modulos, rather than a simple array - perhaps a priority >>>> queue in a Fibonacci heap? >>> >>> >>> Yes, this is the "standard" algorithm I was talking about, in the last >>> post I even mentioned the heuristic you described it the third >>> paragraph. >>> Are you sure you wanted to post it as the answer to my post? >>> >> >> That's not how I understood your post. Though I agree the basic >> algorithm is the same, the details are very different. In particular, > > I did not describe the 'standard' algorithm but explore Richarsd's/fir's > idea about an algorithm without divisions, but writt also without > checking all pairs. > >> your third paragraph suggested Miller-Rabin testing before division, >> which I think would be terribly inefficient. > > Yes, you are right, we do not have to check if A is (pseudo)prime, > and in reality, like you said, M-R test is slower than division. > > This was written that way to resemble 'check all pair', > but yes, it was stupid idea;-) > > bartekltg > There have been a variety of silly ideas in this thread (some intentional, some accidental), as well as some good ones. But no one has come up with a working idea that actually has a chance of factoring a 600 digit number!
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