When Research Papers Had Two Pages And A Few References … But Were Still Great … Lehmann’s…

As a reviewer for a journal, I receive many papers that go on for many pages, and are full of references. But in the end, you often worry…

When Research Papers Had Two Pages And A Few References … But Where Still Great … Lehmann’s Primality Test

As a reviewer for a journal, I receive many papers that go on for many pages and are full of references. But in the end, you often worry about whether the paper is just manufactured to look like a research paper, or whether it has some real contributions. Often you feel that the author could have just said what the wanted to in just a few pages. Merkle’s classic patent on Merkle trees was just a few pages long, for example, but it has since become the foundation of blockchain technology. I read many classic papers from the past, and they would probably struggle to get past the first review, as they don’t follow the current standard for research papers. So, we must worry, that we are creating a research industry which is just going through the motions for many of the research contributions.

In research, it is important to know the core roots of an area, and this often involves diving back to the classic research papers and patents. And, so, with the rise of public-key encryption, and its usage of prime numbers, let’s look at a paper from 1982 [here]:

In the paper, Lehmann comes up with a classic test in his second algorithm:

With his we basically have to test if a number (n) is prime with:

For this, we select random values of a and test the method above. In Python this is just [here]:

a = random.randint(0,100)
res=pow(a,(n-1)//2,n)

and then if the value of res is 1 or -1, the value is a prime number. The more times we try, the more we are certain that it is not a prime number. So we can generate a prime number with a given number of bits, and then generate up to 100 values of a, and test them [here]:

n = getPrime(primebits,randfunc=get_random_bytes)

print (f"Prime number is {n}")
for i in range (1,100):
  a = random.randint(0,100)
  res=pow(a,(n-1)//2,n)
  if (res==1 or res==-1):
    print ("It is prime")
    sys.exit()

print ("It is not likely to be a prime")

A sample run of a 64-bit prime number is:

Prime number is 12510433876576663073
[a=41, res=1] 
It is prime

And for a 256-bit prime number:

Prime number is 73630517144274830036022083609517598134018656346057625372069649877236231727881
[a=71, res=73630517144274830036022083609517598134018656346057625372069649877236231727880] [a=31, res=73630517144274830036022083609517598134018656346057625372069649877236231727880] [a=67, res=73630517144274830036022083609517598134018656346057625372069649877236231727880] [a=61, res=73630517144274830036022083609517598134018656346057625372069649877236231727880] [a=35, res=1] 
It is prime

and:

Prime number is 113207114156106277048908878110721666861685943738291178076336712379377028005541
[a=72, res=113207114156106277048908878110721666861685943738291178076336712379377028005540] [a=23, res=1] 
It is prime

Here is the live code:

Conclusions

There you go. A paper with two pages, and such a great contribution.