“^.?$|^(..+?)\1+$” Detects a Prime Number

The Power of RegEx

“^.?$|^(..+?)\1+$” Detects a Prime Number

The Power of RegEx

As a cybersecurity analyst, what’s one of the best skills you can pick up? Well, knowing how to use regular expressions is certainly well up there in terms of one of the best skills, as they allow us to search for complex patterns. So, let’s do a fun example of finding prime numbers.

Like it or not, your online security is highly dependent on prime numbers. When you connected to this page, there was a key exchange between your browser and the server. This negotiation uses public key encryption — typically with an elliptic curve. This elliptic curve uses a prime number to perform its computation. Also, when you check the identity of a Web site, the Web signs a message with its private key — typically using and RSA or ECDSA signature, and you check with the Web sites public key. Again, these depend on the usage of prime numbers.

But, prime numbers have defeated us in finding a pattern, and there’s no mathematical formula we can use to determine if a number is prime or not. But, there’s a cool little RegEx trick that can find them [here]:

import re
import sys

n=13
if (len(sys.argv)>1):
 n=int(sys.argv[1])

matches=re.match(r'^.?$|^(..+?)\1+$', '1'*n)

print("Use the RegEx of ^.?$|^(..+?)\\1+$\n")
if matches:
 print(f"{n} is not a prime. Match details: {matches.groups()}")
else:
 print(f"{n} is a prime")

If we run we get [here]:

$ python regprime.py 97
Use the RegEx of ^.?$|^(..+?)\1+$

97 is a prime

$ python regprime.py 98
Use the RegEx of ^.?$|^(..+?)\1+$

98 is not a prime. Match details: ('11',)

$ python regprime.py 99
Use the RegEx of ^.?$|^(..+?)\1+$

99 is not a prime. Match details: ('111',)

$ python regprime.py 997
Use the RegEx of ^.?$|^(..+?)\1+$

997 is prime.

We can see that it works for these four values, and where 97 and 997 are prime numbers and 999 is not (as it is 3x3x3x37). A non-prime number is known as a composite number. In the case of 99, we see that we get a match of ‘111’, which means that 3 is a factor.

You can try the following:

How does it work?

First, we create a string of 1s. For a value of 13, we get a string with 13 1's:

1111111111111

Now, ^.?$|^(..+?)\1+$ has two parts: ^.?$ and ^(..+?)\1+$. If the first part fails, we move on to the second part.

The expression ^.?$ with match strings that have ‘0’ or ‘1’ characters. As we are generating a number of 1’s, this will pass and go onto the next part.

With ^(..+?)\1+$, the search will try to match two characters (for the number 2), and then four characters (for the number 4), and so on. This match all the even numbers (and which will not be a prime number — apart from 2). Next, it will try for matches of three characters. For three characters, such as “111”, then “111111”, and so on. If these match, then the number has three as a factor. After this, it will match multiples of 4, multiples of 5, and so on. If it cannot find a match, it will then fail, or get to the end of the possible multiples.

If that fails, it will try to first match 3 characters (corresponds to the number 3), then 6 characters (corresponds to the number 6), then 9 characters, then 12 characters, and so on. This means that it will try to match multiples of 3. If that fails, it proceeds to try to match multiples of 4, then if that fails it will try to match multiples of 5, and so on, until the number whose multiple it tries to match is the length of the string (failure case) or there is a successful match (success case).

You can try the code here:

or here:

https://asecuritysite.com/primes/regprime

Conclusions

The RegEx method is highly inefficient, and will eventually overflow the memory for large prime numbers. So methods are:

  • Miller-Rabin Test for prime. M-R. This outlines Miller-Rabin Test
  • Miller-Rabin Test for Prime Numbers in PowerShell. Miller-Rabin Test. Miller-Rabin Test for Primes is one of the most popular methods for testing for prime numbers used in RSA.
  • Lehmann’s Primality Test. Lehmann’s Primality Test. This outlines Lehmann’s Primality Test.
  • Lehmann’s Primality Test on large primes. Lehmann’s Primality Test. This outlines Lehmann’s Primality Test.
  • Strong prime (Gordon method). Strong prime. This generates a strong prime using the Gordon method.
  • Lucas-Lehmer Test. Lucas-Lehmer Test. Lucas-Lehmer Test for Primality for Mersenne numbers.
  • Solovay-Strassen Primeabilty Test. Solovay-Strassen Primeabilty Test. The Solovay-Strassen test for probable prime numbers.

If you are interested in prime numbers, try:

https://asecuritysite.com/primes