[HP35s] Program for prime number (brut force)
02-17-2019, 05:22 AM
Post: #41
 Gerald H Senior Member Posts: 1,399 Joined: May 2014
RE: [HP35s] Program for prime number (brut force)
(02-16-2019 07:57 PM)Albert Chan Wrote:
(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."

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.

Although the programme may check for

999999

as a factor it does not check for all factors upto 999999.
02-17-2019, 05:46 AM
Post: #42
 Gerald H Senior Member Posts: 1,399 Joined: May 2014
RE: [HP35s] Program for prime number (brut force)
(02-17-2019 04:15 AM)Thomas Klemm Wrote:  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

Thank you for the very interesting statistics, Thomas, you have done more work on that than I have for such small numbers.

Indeed, as the number tested becomes smaller a single test becomes less reliable.

On the 35s my interest is for numbers of the form

(5 or 6 digit prime)*(5 or 6 digit prime)

& for such the programme as is has been satisfactory.

It would be very nice of you if you could produce statistics for numbers in that range.

The programme at

contains some useful calculations & sadly no users, if indeed there are any, have suggested improvements - perhaps you could assist?
02-17-2019, 04:33 PM (This post was last modified: 02-17-2019 04:37 PM by Gerald H.)
Post: #43
 Gerald H Senior Member Posts: 1,399 Joined: May 2014
RE: [HP35s] Program for prime number (brut force)
"Although the programme may check for

999999

as a factor it does not check for all factors upto 999999."

Not correct, sorry - To some degree the programme does check for all factors up to 999999.

eg If you enter

55021677489

the programme very quickly finds its largest factor & returns

0
02-17-2019, 10:58 PM (This post was last modified: 02-17-2019 11:47 PM by Albert Chan.)
Post: #44
 Albert Chan Senior Member Posts: 548 Joined: Jul 2018
RE: [HP35s] Program for prime number (brut force)
Trivia: searching backwards, found a particular bad composite, with many SPRP non-witnesses.

N = 999999 512881 = 881917 * 1133893 = A*B

For PRP test:
Total PRP non-witnesses = gcd(A-1,N-1) gcd(B-1,N-1) = 125988 * 125988 = 15872 976144
Percent of hitting PRP non-witness = (125988² - 2) / (N-3) ≈ 1.59%

For SPRP test:
Tried first 10 million bases, SPRP non-witnesses = 59708
Percent of hitting SPRP non-witness ≈ 59708/1e7 ≈ 0.60%

Note: 0.60% assumed statstical trend continued all the way to N-2
02-18-2019, 06:09 AM
Post: #45
 Gerald H Senior Member Posts: 1,399 Joined: May 2014
RE: [HP35s] Program for prime number (brut force)
(02-17-2019 10:58 PM)Albert Chan Wrote:  Trivia: searching backwards, found a particular bad composite, with many SPRP non-witnesses.

N = 999999 512881 = 881917 * 1133893 = A*B

For PRP test:
Total PRP non-witnesses = gcd(A-1,N-1) gcd(B-1,N-1) = 125988 * 125988 = 15872 976144
Percent of hitting PRP non-witness = (125988² - 2) / (N-3) ≈ 1.59%

For SPRP test:
Tried first 10 million bases, SPRP non-witnesses = 59708
Percent of hitting SPRP non-witness ≈ 59708/1e7 ≈ 0.60%

Note: 0.60% assumed statstical trend continued all the way to N-2

A very nice example of a difficult case - But the chance of testing this number, or any other constructed to be difficult cases, when feeding the programme a random number is very small.

Similarly the likelihood of finding a number as in posting #43 is very small.
 « Next Oldest | Next Newest »

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