[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin) - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: [HP35s] Program for prime number (Wheel Sieve and Miller-Rabin) (/thread-12406.html) |
RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 10:45 AM (02-13-2019 11:53 AM)Thomas Klemm Wrote: You may want to have a look at (35S) Number Theory Library. Yes, PRIME? calls RABIN? to one random base after first checking for small factors of A. RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 11:16 AM The PRIME? programme in http://www.hpmuseum.org/forum/thread-4236.html for input 999 999 999 989 returns 1 ie entry is prime, in 36 seconds. RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019 11:36 AM (02-11-2019 05:16 PM)fred_76 Wrote: (02-16-2019 11:16 AM)Gerald H Wrote: for input 999 999 999 989 returns 1 ie entry is prime, in 36 seconds. Impressive: That's 9138 ÷ 36 = 253.83 times faster. RE: [HP35s] Program for prime number (brut force) - fred_76 - 02-16-2019 11:48 AM (02-16-2019 11:36 AM)Thomas Klemm Wrote:(02-11-2019 05:16 PM)fred_76 Wrote: True ! But I’m pretty sure it can still be optimized. I can’t do that right now. See you in 2-3 weeks... RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019 11:57 AM (02-16-2019 10:45 AM)Gerald H Wrote: Yes, PRIME? calls RABIN? to one random base after first checking for small factors of A. Thus in case of 1 we only know that it's a strong probable prime. But we could be sure by checking the bases 2, 13, 23, and 1662803. Cheers Thomas RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 12:54 PM (02-16-2019 11:57 AM)Thomas Klemm Wrote:(02-16-2019 10:45 AM)Gerald H Wrote: Yes, PRIME? calls RABIN? to one random base after first checking for small factors of A. Please report a number falsely returned as prime. RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019 02:12 PM (02-16-2019 12:54 PM)Gerald H Wrote: Please report a number falsely returned as prime. Example: Quote:Suppose we wish to determine if n = 221 is prime. But 221 = 13×17, so it's not a prime. Quote:It can be shown that for any odd composite n, at least 3/4 of the bases a are witnesses for the compositeness of n. Thus chances are that a composite number is falsely considered a prime if we run the test only once. I would expect this to happen if you run the program multiple times with the same composite number. Cheers Thomas RE: [HP35s] Program for prime number (brut force) - fred_76 - 02-16-2019 02:22 PM (02-16-2019 12:54 PM)Gerald H Wrote:It seems hard because the algorithm uses a random test. Therefore on number may be missed one time but not the other time. By testing 2/13/23/1662803, you are sure that (up to 12 digits) your number is prime or composite.(02-16-2019 11:57 AM)Thomas Klemm Wrote: Thus in case of 1 we only know that it's a strong probable prime. RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-16-2019 02:29 PM (02-16-2019 10:45 AM)Gerald H Wrote: Yes, PRIME? calls RABIN? to one random base after first checking for small factors of A. Just checking, when you say random base, you meant 2 to A-2 ? Technically, this is a composite test. Any number that failed is *guaranteed* composite. The reverse is not always true: strong pseudoprimes Thus, we use pre-selected set of bases, to cover each other's "holes", to prove primality. Baillie-PSW primality test (SPRP + Lucas test) covered the "holes" even better. There is an award of $30 to show an example of pseudoprime. RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 05:39 PM (02-16-2019 02:12 PM)Thomas Klemm Wrote:(02-16-2019 12:54 PM)Gerald H Wrote: Please report a number falsely returned as prime. "Chances are..." - No. "At least 3/4 of bases are witnesses..." - Yes, but how many are in fact witnesses? The "at least" allows the likelihood that many more than 3/4 are witnesses, & that is in fact generally the case. Set at random N := 803189 * 485909 the product of two primes, how many bases are actually witnesses? Try running PRIME?, I will be very surprised if the 35s is fast enough for you to repeat the test until a 1 appears. I use one test as it's reliable enough - Certainty is expensive, if you're really not sure try running the programme again. For larger numbers, say 2^555 range, one test gives certainty. RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 05:43 PM Additionally, PRIME? removes 221 via the small factors test. RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019 05:57 PM This is a list of composite numbers \(n < 10000\) with the amount of strong liars \(k\) and the ratio \(r=\frac{n-3}{k}\): Code: r n k Thus I suggest to run PRIME? multiple time with 1891 and see how long it takes until you hit a strong liar. Cheers Thomas RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 05:59 PM (02-16-2019 05:57 PM)Thomas Klemm Wrote: This is a list of composite numbers \(n < 10000\) with the amount of strong liars \(k\) and the ratio \(r=\frac{n-3}{k}\): 1891 will not get that far, declared composite by the small factors test. RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019 06:07 PM (02-16-2019 05:39 PM)Gerald H Wrote: 1891 will not get that far, declared composite by the small factors test. So what's the biggest of your small factors that you test? RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 06:18 PM (02-16-2019 06:07 PM)Thomas Klemm Wrote:(02-16-2019 05:39 PM)Gerald H Wrote: 1891 will not get that far, declared composite by the small factors test. Have you actually had a look at or used the programme on the 35s? Should you inspect the programme you'll find the largest small factor that is tested for is 999999 RE: [HP35s] Program for prime number (brut force) - Gerald H - 02-16-2019 07:09 PM "Set at random N := 803189 * 485909 the product of two primes, how many bases are actually witnesses? Try running PRIME?, I will be very surprised if the 35s is fast enough for you to repeat the test until a 1 appears." The use of "witness" above is correct, most bases return 0 for input N & are thus "witnesses". Please post any comments in this thread for the benefit of all. RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-16-2019 07:57 PM (02-16-2019 07:09 PM)Gerald H Wrote: "Set at random Re-reading your quote, I was mistaken. I read a bit too fast, and think you are saying until 1 [witness] appears. Changing the word witness to non-witness made the statement un-ambiguous. "Until 1 pseduoprime appears" also work. (02-16-2019 06:18 PM)Gerald H Wrote: Should you inspect the programme you'll find the largest small factor that is tested for is If the code checked this far, why the need for SPRP test ? Any 12 digits integer, with small factor upto 999999 checked, already proved primality. RE: [HP35s] Program for prime number (brut force) - Thomas Klemm - 02-16-2019 08:39 PM (02-16-2019 05:39 PM)Gerald H Wrote: Set at random It could very well be that this number has no strong liars. (02-16-2019 06:18 PM)Gerald H Wrote: Have you actually had a look at or used the programme on the 35s? I had a look at the program but wasn't able to follow. Even if the batteries of my HP-35s weren't dead I doubt I would enter an 850 line program just to figure that out by myself. Quote:Should you inspect the programme you'll find the largest small factor that is tested for is Not sure if I understood that correctly but I checked products \(n = p \cdot q\) of primes \(p, q > 1000\). So they shouldn't be detected by testing small factors. Code: r n k Chances might be small with \(1102837=1009×1093\) to hit a strong liar but they are not 0. I was only aware of the upper bound of the probability \(p<\frac{1}{4}\) but not of the exact distribution. Cheers Thomas RE: [HP35s] Program for prime number (brut force) - Albert Chan - 02-16-2019 10:32 PM (02-16-2019 05:57 PM)Thomas Klemm Wrote: Before n is strong pseduoprime, it must be a Fermat pseduoprime. Let p1, ... pk be distinct prime factors of N: Number of bases (mod N) = gcd(p1-1, N-1) ... gcd(pk-1, N-1) So, picking top 2 numbers from the list: 1891 = 31 * 61, gcd(30, 1890) * gcd(60, 1890) = 30 * 30 = 900 8911 = 7*19*67, gcd(6, 8910) * gcd(18, 8910) * gcd(66, 8910) = 6 * 18 * 66 = 7128 No wonder so many strong pseudoprimes. Gerald H's example, N = 803189 * 485909 gcd(N-1, 803188) * gcd(N-1, 485908) = 4*4 = 16 Removing 2 trivial bases of ±1, you are down to 14 Some Fermat pseudoprimes might not survive the strong test, so possibly few strong pseudoprimes. RE: [HP35s] Program for prime number (brute force) - Thomas Klemm - 02-17-2019 04:15 AM Meanwhile I extended the search a bit: Code: r n k For \(1563151=1021×1531\) or \(1844267=1109×1663\) it's realistic to hit a strong liar after a few attempts. Cheers Thomas |