(02-13-2019 11:53 AM)Thomas Klemm Wrote: [ -> ]You may want to have a look at (35S) Number Theory Library.

There are the following functions:

Quote:PRIME? 148

A -> 0 OR 1 as A is composite or probably prime.

RABIN? 571

A, B -> 0 or 1, 1 if A is a strong pseudo-prime base B, 0 if not.

Though I haven't tried but if PRIME? uses RABIN? (which I assume implements the Miller-Rabin Primality Test) it might be considerably faster for bigger numbers.

I've implemented this for the HP-48GX:

(48G) Miller-Rabin Primality Test

This article gives a bit more details:

Miller-Rabin Primality Test for the HP-48

Cheers

Thomas

Yes, PRIME? calls RABIN? to one random base after first checking for small factors of A.

(02-11-2019 05:16 PM)fred_76 Wrote: [ -> ]PHP Code:

`Digits Prime Number Total Time`

12 digits 999 999 999 989 02:32:18

(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.

(02-16-2019 11:36 AM)Thomas Klemm Wrote: [ -> ] (02-11-2019 05:16 PM)fred_76 Wrote: [ -> ]PHP Code:

`Digits Prime Number Total Time`

12 digits 999 999 999 989 02:32:18

(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.

True ! But I’m pretty sure it can still be optimized. I can’t do that right now. See you in 2-3 weeks...

(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

(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.

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

Please report a number falsely returned as prime.

(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.

We randomly select a number a such that 1 < a < n - 1, say a = 174.

…

Since 220 ≡ −1 mod n, either 221 is prime, or 174 is a strong liar for 221.

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

(02-16-2019 12:54 PM)Gerald H Wrote: [ -> ] (02-16-2019 11:57 AM)Thomas Klemm Wrote: [ -> ]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

Please report a number falsely returned as prime.

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 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.

(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.

Example:

Quote:Suppose we wish to determine if n = 221 is prime.

We randomly select a number a such that 1 < a < n - 1, say a = 174.

…

Since 220 ≡ −1 mod n, either 221 is prime, or 174 is a strong liar for 221.

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

"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.

Additionally, PRIME? removes 221 via the small factors test.

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`

4.21 1891 448

5.00 8911 1780

5.57 2701 484

6.18 6533 1056

6.20 5461 880

6.41 1541 240

8.22 8321 1012

8.33 4033 484

8.52 2047 240

8.65 1387 160

Thus I suggest to run

PRIME? multiple time with

1891 and see how long it takes until you hit a strong liar.

Cheers

Thomas

(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}\):

Code:

` r n k`

4.21 1891 448

5.00 8911 1780

5.57 2701 484

6.18 6533 1056

6.20 5461 880

6.41 1541 240

8.22 8321 1012

8.33 4033 484

8.52 2047 240

8.65 1387 160

Thus I suggest to run PRIME? multiple time with 1891 and see how long it takes until you hit a strong liar.

Cheers

Thomas

1891 will not get that far, declared composite by the small factors test.

(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?

(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.

So what's the biggest of your small factors that you 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

"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.

(02-16-2019 07:09 PM)Gerald H Wrote: [ -> ]"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."

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

999999

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.

(02-16-2019 05:39 PM)Gerald H Wrote: [ -> ]Set at random

N := 803189 * 485909

the product of two primes, how many bases are actually witnesses?

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

999999

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`

417.11 1102837 2644

1012.01 1018081 1006

1016.01 1026169 1010

1022.01 1038361 1016

1024.01 1042441 1018

1034.01 1062961 1028

1036.01 1067089 1030

1042.01 1079521 1036

1052.01 1100401 1046

1054.01 1104601 1048

1064.01 1125721 1058

1066.01 1129969 1060

1072.01 1142761 1066

1090.01 1181569 1084

1094.01 1190281 1088

1096.01 1194649 1090

1100.01 1203409 1094

1205.06 1060459 880

1305.39 1148743 880

2395.24 1073071 448

5317.83 1042297 196

6703.52 1072567 160

7319.45 1083281 148

…

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

(02-16-2019 05:57 PM)Thomas Klemm Wrote: [ -> ]
Code:

` r n k`

4.21 1891 448

5.00 8911 1780

5.57 2701 484

6.18 6533 1056

6.20 5461 880

6.41 1541 240

8.22 8321 1012

8.33 4033 484

8.52 2047 240

8.65 1387 160

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.

Meanwhile I extended the search a bit:

Code:

` r n k`

12.02 1563151 130048

12.02 1844267 153456

16.02 1911397 119284

16.03 1600117 99844

30.05 1968557 65520

32.05 1663213 51892

32.06 1389581 43348

35.77 1922801 53748

40.06 2078737 51892

40.07 1333603 33280

43.71 1777793 40676

53.41 2102437 39364

60.09 1999759 33280

60.10 1589531 26448

60.11 1275347 21216

70.10 2121013 30256

70.12 1546021 22048

84.15 1455451 17296

93.50 1459009 15604

…

For \(1563151=1021×1531\) or \(1844267=1109×1663\) it's realistic to hit a strong liar after a few attempts.

Cheers

Thomas