Re: [pqc-forum] Question: Prime Numbers in Lattice-Based Cryptography and FHE

[Jacob Alperin-Sheriff]

Usually only ones that fit into a 64-bit register with a little room to spare are used, this is a very weirdly phrased question  though. 

-Jacob Alperin-Sheriff

(609) 240-9132

On Mon, Sep 9, 2024 at 12:28 PM ahmed alotaibi <alou...@gmail.com> wrote:

Hello,

I am researching lattice-based cryptography and fully homomorphic encryption, and I have a question regarding the use of prime numbers in these systems.

Specifically, I am interested in whether the following prime numbers are used in lattice-based cryptographic schemes, such as fully homomorphic encryption:

2^61 - 61

2^64 - 2^32 - 1

2^61 - 61

2^64 - 2^32 - 1

2^1024 - 2^960 - 1

Could you provide any insights or references on whether these primes are employed in known implementations or schemes? Additionally, if there are other prime numbers of similar magnitude (larger than 40 bits or 64 bits) used in lattice-based cryptography, I would appreciate any information on those as well.

Thank you!

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/467dd79b-3829-4b18-becb-eba35f3f275bn%40list.nist.gov.

[Michael Scott]

You possibly meant 2^61-1 and 2^64-2^32+1

Is there a name for primes of the form 2^n-n ??

Mike

On Mon, Sep 9, 2024 at 5:53 PM Michael Scott <mike....@miracl.com> wrote:

Those numbers are not primes..

2^61-61 =  29 × 17729 × 4484845 614751

Mike

[Michael Scott]

[Michael Scott]

I quite like 2^261-261

Mike

[Noah Stephens-Davidowitz]

Hi Ahmed,

I'm not sure why you're specifically interested in this, but it seems worth noting that none of your numbers are prime.