Ask Your Question
1

How would I be able to check if a given number is a solinas prime?

asked 2019-04-24 08:39:45 +0200

jonathansmith gravatar image

updated 2019-06-20 13:10:30 +0200

FrédéricC gravatar image

Using sage, how would I be able to check whether a given number is a general mersenne prime, or if possible any other special primes?

In particular, looking to check for special primes p such that modulo p is easy to calculate

edit retag flag offensive close merge delete

Comments

Regarding your question

  • what is a "special prime"?
  • what do you mean by "modulo p is easy to calculate"?
vdelecroix gravatar imagevdelecroix ( 2019-04-27 22:38:49 +0200 )edit

1 Answer

Sort by » oldest newest most voted
0

answered 2019-04-29 00:34:13 +0200

slelievre gravatar image

The "Solinas prime" wikipedia page says a Solinas prime is a prime of the form f(2^m) where f is a polynomial of low degree, and gives a few examples.

Hint: observe the structure of bits of each of these primes:

sage: l = [
....:         2^192 - 2^64 - 1,
....:         2^224 - 2^96 + 1,
....:         2^256 - 2^224 + 2^192 + 2^96 - 1,
....:         2^384 - 2^128 - 2^96 + 2^32 - 1,
....:         2^448 - 2^224 - 1
....:     ]
sage: for p in l:
....:     print(p.bits())

Then define a function to detect m and the polynomial from the bit structure.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-04-24 08:36:50 +0200

Seen: 512 times

Last updated: Apr 29 '19