Month: February 2024

I’ve been experimenting with S. Khashin’s Frobenius primality test, as described in a preprint of his, Counterexamples for Frobenius primality test, at https://arxiv.org/abs/1307.7920 . Given an odd number n>1 that is not a square, let c be an odd prime number with (c/n)=-1, (c/n) being the Jacobi symbol. If n is prime, then (1+sqrt(c))^n ==… Continue reading The Frobenius Test Finds No Liars Below 2000 Among the First Million Test Numbers

The Frobenius primality test is an algebraic type primality test which perhaps deserves to be better known. Like other tests, it is sure to label genuine prime numbers as prime, but is liable to misidentify some composite numbers as primes. The test was first described by Jon Grantham in a 1998 preprint. There are a… Continue reading Prime Deception: Counting Liars for the Fermat, Miller-Rabin and Frobenius Primality Tests

I’ve collected in one spot the functions for using Sergey Khashin’s Frobenius primality test. The idea of a Frobenius test is due to Jon Grantham.

I’m posting this so I can refer to it later. The number being tested is n=(82065^19937 -1)/(82065-1). This is one part of a Miller-Rabin strong primality test. One checks that diff is -1, then one replaces the 32 on line 3 of the script by 16, and the value of res ought to be 1.… Continue reading An OpenPFGW script that does a partial Miller-Rabin test on a large number

Given an odd number N with k bits where k>=2, we can ask for the nearest k-bit prime p in Hamming distance, that is the number of bit positions where p and N in base 2 differ. Up to 2×10^9, I get distances of 2 or less. Therefore, among the set P_N = { primes… Continue reading Odd numbers below 2e9 and close primes in Hamming distance (Updated)