Exetools  

Go Back   Exetools > General > Source Code

Notices

Reply
 
Thread Tools Display Modes
  #1  
Old 08-10-2021, 23:31
CodeCracker CodeCracker is offline
VIP
 
Join Date: Jun 2011
Posts: 454
Rept. Given: 27
Rept. Rcvd 398 Times in 129 Posts
Thanks Given: 21
Thanks Rcvd at 1,823 Times in 349 Posts
CodeCracker Reputation: 300-399 CodeCracker Reputation: 300-399 CodeCracker Reputation: 300-399 CodeCracker Reputation: 300-399
GenerateBigPrimes src VC6

Original project here:
http://codes-sources.commentcamarche...chiffresAuteur
the project uses naive multiplication approach, so isn't fast!

added decimal string conversion functions:
BigInt na = BigInt::BigIntFromDecStr("4294967295");
std::string str = na.GetDecStrValue();
Attached Files
File Type: zip GenerateBigPrimes_srcVC6.zip (45.6 KB, 16 views)
Reply With Quote
The Following 3 Users Say Thank You to CodeCracker For This Useful Post:
niculaita (08-11-2021), Zeocrack (10-04-2022)
  #2  
Old 08-12-2021, 09:38
chants chants is online now
VIP
 
Join Date: Jul 2016
Posts: 725
Rept. Given: 35
Rept. Rcvd 48 Times in 30 Posts
Thanks Given: 666
Thanks Rcvd at 1,050 Times in 475 Posts
chants Reputation: 48
Montgomery multiplication would significantly reduce the run time especially for the modular exponentiation in Miller Rabin primarily testing.

Further modular exponentiation here is naive as it could use windowing of the exponent into groups of bits at a time to reduce the products by a decent amount though squarings remains constant.

Ideally you generate a few dozen numbers and test them for primarily in batches. This way the modular exponentation precomputed table is efficiently applied to all the different exponents simultaneously.

There are also ways to do GCD and modular inverse without divisions using montgomery multiplication and even powers of 2 based on the machine word size. And yes of course at a certain bit size Karatsuba or Schonhage Strassen multiplication should be used. Other tricks are possible such as looking at consecutive ones in the multiplicand and dealing with primes of forms 2^n-2^m+... by doing addition and subtraction which is far better than pure addition in grade school method.

Isnt the OpenSSL open source library considered the de facto reference for a reasonably heavily optimized big prime finder?
Reply With Quote
The Following 3 Users Say Thank You to chants For This Useful Post:
Abaddon (08-25-2021), niculaita (08-12-2021)
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On



All times are GMT +8. The time now is 17:56.


Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX, chessgod101
( 1998 - 2024 )