### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: random LARGE prime numbers  (Read 795 times)

#### Raul_ES

• Full Member
• Posts: 174
• My interests: Healthcare & Computers
##### random LARGE prime numbers
« on: February 13, 2020, 12:24:55 am »
Hello friends,

I am struggling trying to implement Diffie-Hellman's protocol in a network  application I am working on. As far as I know, it's recommended to use large prime values for the "p" variable of the algorithm. I've read in some articles p must be over 600 digits to ensure it remains unbreakable.

https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange

I would like to hear your experience with the protocol itself and if you know any good implementation of it.

The question: how do you generate random prime numbers with at least 600 digits?

With the following code I can generate a list of prime numbers up to n. But I believe it to be not a good solution for what I ask, having to generate a list  each time and picking up the numbers with the size desired, I am confused.  Please, let me see what you think.

Code: Pascal  [Select][+][-]
1. {**********************************
2.      Criba de Eratóstenes
3. ***********************************
4.
5. Debo usar un vector dinámico que crezca en función de la cantidad de números
6. primos que la criba haya podido generar. Cada vez que se genere un primo,
7. mediante setLength(array, i = i + 1) incrementamos en 1 la longitud del array.
8.
9. Al redimensionar un array se mantiene lo anterior si se incrementa o encoje,
10. pero siempre se pierde lo posterior.
11. }
12.
13. function GeneratePrimeNumberList( topNumber : integer ):array of integer;
14. var
15. i,j,lengthArray:integer;
16. primeFlag:boolean;
18.
19. begin
20. lengthArray := 0;
21.
22. for j := 2 to topNumber do
23.   begin
24.     i := 2; primeFlag := true;
25.     while i <= (j div 2) do
26.        begin
27.           if (j mod i) = 0 then
28.               primeFlag := false;
29.               i := i + 1;
30.        end;
31.     if primeFlag = true then
32.        begin
33.          lengthArray := lengthArray + 1;
36.        end;
37.   end;
39. end;

Do you know any other better way?

regards
« Last Edit: February 13, 2020, 10:51:19 pm by Raul_ES »
Pharmacy + Chemistry + Biology + Healthcare + Computing

If you have any interest or project related with these areas feel free to contact me!

#### eljo

• Sr. Member
• Posts: 408
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #1 on: February 13, 2020, 02:59:54 am »
there is no native numeric data type that can support 600 digits.
According to http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm (x=2 y=2048 press the x^y button, I haven't tested the results so the conclusion might be wrong) you need 2048 bits to be able to hold 600 digit numbers, which requires you to use some short of arbitrary precision numeric library (bigint, bigdecimal etc) to hold your results.

Having said unless the goal of your project is to calculate huge prime number, I would advice use an array of known primes over the 600 digit mark to randomly select one of them, after all the primes do not change and the array can be updated / replaced in time.
Also you should change the above routine and add a starting value too, it will constrain the range of calculations.

#### Xor-el

• Sr. Member
• Posts: 408
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #2 on: February 13, 2020, 08:31:33 am »
@Raul_ES, why not use a library designed for that specific task instead of implementing it from the scratch.

#### Hartmut

• Sr. Member
• Posts: 435
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #3 on: February 13, 2020, 12:08:19 pm »
I would advice use an array of known primes over the 600 digit mark to randomly select one of them, after all the primes do not change and the array can be updated / replaced in time.
If that solution is possible for you, you can find a lot of websites containing lists of big primes by google for e.g. +big +prime +numbers +lists

#### winni

• Hero Member
• Posts: 1807
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #4 on: February 13, 2020, 01:06:00 pm »
Hi!

https://primes.utm.edu/

The University of Tennessee has some lists:

* The 5000 largest known primes
*  The first 50,000,000 primes
* and, and ....

Winni

#### Raul_ES

• Full Member
• Posts: 174
• My interests: Healthcare & Computers
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #5 on: February 13, 2020, 10:09:10 pm »
Thank you @winni, I didn't know that website. That page has lots of information and many number lists ready to be used. Great!
Pharmacy + Chemistry + Biology + Healthcare + Computing

If you have any interest or project related with these areas feel free to contact me!

#### Raul_ES

• Full Member
• Posts: 174
• My interests: Healthcare & Computers
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #6 on: February 13, 2020, 10:12:58 pm »
@Raul_ES, why not use a library designed for that specific task instead of implementing it from the scratch.

I think sometimes reinventing-the-wheel is a great way to learn programming, computing and also maths. By the way, I don't know of any pascal library or unit for this kind of stuff (but sure there is one somewhere!). thanks.
Pharmacy + Chemistry + Biology + Healthcare + Computing

If you have any interest or project related with these areas feel free to contact me!

#### Raul_ES

• Full Member
• Posts: 174
• My interests: Healthcare & Computers
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #7 on: February 13, 2020, 10:22:01 pm »
I would advice use an array of known primes over the 600 digit mark to randomly select one of them, after all the primes do not change and the array can be updated / replaced in time.
If that solution is possible for you, you can find a lot of websites containing lists of big primes by google for e.g. +big +prime +numbers +lists

Thanks Harmut, I thought about generating a list and store it to a file and read from it when needed. Easier would be to get an allready  prepared list but I am not sure about how to manage such large lists of such large numbers. It is something new for me.
Pharmacy + Chemistry + Biology + Healthcare + Computing

If you have any interest or project related with these areas feel free to contact me!

#### Raul_ES

• Full Member
• Posts: 174
• My interests: Healthcare & Computers
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #8 on: February 13, 2020, 10:41:29 pm »
there is no native numeric data type that can support 600 digits.
According to http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm (x=2 y=2048 press the x^y button, I haven't tested the results so the conclusion might be wrong) you need 2048 bits to be able to hold 600 digit numbers, which requires you to use some short of arbitrary precision numeric library (bigint, bigdecimal etc) to hold your results.

that numbers have such size that is overwhelming. I'm not used to work with such a size. I will do more research to learn how to manage them. Thanks for the info :-)

Quote
Having said unless the goal of your project is to calculate huge prime number, I would advice use an array of known primes over the 600 digit mark to randomly select one of them, after all the primes do not change and the array can be updated / replaced in time.
Also you should change the above routine and add a starting value too, it will constrain the range of calculations.

I though something similar. To read them from a large list in a file and put them in an array of "what type here?".

I have just discovered the sieve of Atkin, another numerical method to find primes that improves Erathosthenes in terms of asymptotic complexity.

https://en.wikipedia.org/wiki/Sieve_of_Atkin

Pharmacy + Chemistry + Biology + Healthcare + Computing

If you have any interest or project related with these areas feel free to contact me!

#### winni

• Hero Member
• Posts: 1807
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #9 on: February 13, 2020, 10:45:14 pm »
Hi!

I don't know if there is somewhere a unit to handle BCDs around, but that would help.

BCD are Binary Coded Digits which means that for every digit there is needed  a nibble = 4 bits = byte div 2

BCDs are much more near to the human way of counting and computing. And you can connect them to a long chain of digts.

Winni

« Last Edit: February 13, 2020, 10:48:08 pm by winni »

#### Raul_ES

• Full Member
• Posts: 174
• My interests: Healthcare & Computers
##### Re: random LARGE prime numbers
« Reply #10 on: February 13, 2020, 10:52:22 pm »
I also found this interesting article by our fellow @Thaddy:

https://wiki.freepascal.org/A_simple_implementation_of_the_Mersenne_twister
Pharmacy + Chemistry + Biology + Healthcare + Computing

If you have any interest or project related with these areas feel free to contact me!

#### Raul_ES

• Full Member
• Posts: 174
• My interests: Healthcare & Computers
##### Re: random LARGE prime numbers
« Reply #11 on: February 14, 2020, 12:00:07 am »
« Last Edit: February 14, 2020, 12:02:07 am by Raul_ES »
Pharmacy + Chemistry + Biology + Healthcare + Computing

If you have any interest or project related with these areas feel free to contact me!

#### eljo

• Sr. Member
• Posts: 408
##### Re: random LARGE prime numbers (not Mersenne)
« Reply #12 on: February 14, 2020, 03:01:51 am »
Hi!

I don't know if there is somewhere a unit to handle BCDs around, but that would help.

take a look on FmtBCD unit that comes with fpc.