[HP35s] Program for prime number (Wheel Sieve and MillerRabin)

02162019, 10:45 AM
Post: #21




RE: [HP35s] Program for prime number (brut force)
(02132019 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. 

02162019, 11:16 AM
Post: #22




RE: [HP35s] Program for prime number (brut force)
The PRIME? programme in
http://www.hpmuseum.org/forum/thread4236.html for input 999 999 999 989 returns 1 ie entry is prime, in 36 seconds. 

02162019, 11:36 AM
Post: #23




RE: [HP35s] Program for prime number (brut force)  
02162019, 11:48 AM
Post: #24




RE: [HP35s] Program for prime number (brut force)
(02162019 11:36 AM)Thomas Klemm Wrote:(02112019 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 23 weeks... 

02162019, 11:57 AM
Post: #25




RE: [HP35s] Program for prime number (brut force)
(02162019 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 

02162019, 12:54 PM
Post: #26




RE: [HP35s] Program for prime number (brut force)
(02162019 11:57 AM)Thomas Klemm Wrote:(02162019 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. 

02162019, 02:12 PM
Post: #27




RE: [HP35s] Program for prime number (brut force)
(02162019 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 

02162019, 02:22 PM
Post: #28




RE: [HP35s] Program for prime number (brut force)
(02162019 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.(02162019 11:57 AM)Thomas Klemm Wrote: Thus in case of 1 we only know that it's a strong probable prime. 

02162019, 02:29 PM
(This post was last modified: 02162019 03:02 PM by Albert Chan.)
Post: #29




RE: [HP35s] Program for prime number (brut force)
(02162019 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 A2 ? Technically, this is a composite test. Any number that failed is *guaranteed* composite. The reverse is not always true: strong pseudoprimes Thus, we use preselected set of bases, to cover each other's "holes", to prove primality. BailliePSW primality test (SPRP + Lucas test) covered the "holes" even better. There is an award of $30 to show an example of pseudoprime. 

02162019, 05:39 PM
(This post was last modified: 02162019 05:42 PM by Gerald H.)
Post: #30




RE: [HP35s] Program for prime number (brut force)
(02162019 02:12 PM)Thomas Klemm Wrote:(02162019 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. 

02162019, 05:43 PM
Post: #31




RE: [HP35s] Program for prime number (brut force)
Additionally, PRIME? removes 221 via the small factors test.


02162019, 05:57 PM
Post: #32




RE: [HP35s] Program for prime number (brut force)
This is a list of composite numbers \(n < 10000\) with the amount of strong liars \(k\) and the ratio \(r=\frac{n3}{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 

02162019, 05:59 PM
Post: #33




RE: [HP35s] Program for prime number (brut force)
(02162019 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{n3}{k}\): 1891 will not get that far, declared composite by the small factors test. 

02162019, 06:07 PM
Post: #34




RE: [HP35s] Program for prime number (brut force)  
02162019, 06:18 PM
Post: #35




RE: [HP35s] Program for prime number (brut force)
(02162019 06:07 PM)Thomas Klemm Wrote:(02162019 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 

02162019, 07:09 PM
Post: #36




RE: [HP35s] Program for prime number (brut force)
"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. 

02162019, 07:57 PM
(This post was last modified: 02162019 08:52 PM by Albert Chan.)
Post: #37




RE: [HP35s] Program for prime number (brut force)
(02162019 07:09 PM)Gerald H Wrote: "Set at random Rereading 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 nonwitness made the statement unambiguous. "Until 1 pseduoprime appears" also work. (02162019 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. 

02162019, 08:39 PM
Post: #38




RE: [HP35s] Program for prime number (brut force)
(02162019 05:39 PM)Gerald H Wrote: Set at random It could very well be that this number has no strong liars. (02162019 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 HP35s 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 

02162019, 10:32 PM
(This post was last modified: 02162019 10:40 PM by Albert Chan.)
Post: #39




RE: [HP35s] Program for prime number (brut force)
(02162019 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(p11, N1) ... gcd(pk1, N1) 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(N1, 803188) * gcd(N1, 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. 

02172019, 04:15 AM
Post: #40




RE: [HP35s] Program for prime number (brute force)
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 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)