Post Reply 
[HP35s] Program for prime number (brut force)
02-17-2019, 05:22 AM
Post: #41
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."

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.

Although the programme may check for

999999

as a factor it does not check for all factors upto 999999.
Find all posts by this user
Quote this message in a reply
02-17-2019, 05:46 AM
Post: #42
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

http://www.hpmuseum.org/forum/thread-4236.html

contains some useful calculations & sadly no users, if indeed there are any, have suggested improvements - perhaps you could assist?
Find all posts by this user
Quote this message in a reply
02-17-2019, 04:33 PM (This post was last modified: 02-17-2019 04:37 PM by Gerald H.)
Post: #43
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
Find all posts by this user
Quote this message in a reply
02-17-2019, 10:58 PM (This post was last modified: 02-17-2019 11:47 PM by Albert Chan.)
Post: #44
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
Find all posts by this user
Quote this message in a reply
02-18-2019, 06:09 AM
Post: #45
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.
Find all posts by this user
Quote this message in a reply
Post Reply 




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