2

I am programming prime number generator (max 200 digits) in Pascal using the Miller–Rabin primality test.

I have already implemented multiple steps but I got stuck at the modular exponentiation part. I chose the Right-to-left binary method where (I assume) I have to implemenent A mod B where A and B are both (in worst case 200 digits). And to calculate the modulus I have to implement division of 2 numbers with max 200 digits. I respresent my long integers in an array where every element is a digit (0-9).

I have googled and I have not found any suitable algorithm for me (that would not take a lot of time to implement). So I am asking here if anyone has any experience with this. I doesnt have to be the fastest algorithm but it should not be "dumb" as euclidian divison that would take years and should be kind of easy to implement. I dont want do use any library (pure pascal)

honzaik
  • 273
  • 1
  • 10
  • Why are you storing them in base 10? – cdo256 Jul 15 '17 at 11:00
  • 1
    no particular reason except its base 10 where I can think easily and I dont have to implement base 10 to binary and back. Everything I implemented until this worked easily with base 10. I guess it wouldnt be a problem to convert it into binary if there is a relatively simple algorithm that works in binary – honzaik Jul 15 '17 at 11:07
  • 1
    If you don't care about efficiency and don't want to directly implement full division -- implement multiplication if you haven't already done so, implement division by 2 (a special case which is easy to work out), and then use binary search to find the integer quotient. – John Coleman Jul 15 '17 at 11:17
  • 1
    Related: https://stackoverflow.com/q/5386377/4996248 – John Coleman Jul 15 '17 at 11:23
  • @JohnColeman yes i have already implemented those 2 functions. What do you mean by that specifically. I skimmed throught that page you linked and I'm not sure what you are refering to. Is it [this answer](https://stackoverflow.com/a/5387432/3163091)? – honzaik Jul 15 '17 at 11:40
  • The question itself outlines what I meant by division by binary search. The answers to the question are about better methods, which are methods which you seem to want to avoid. – John Coleman Jul 15 '17 at 11:56
  • [bignum algorithms](https://github.com/bitkeeper-scm/tcl/blob/master/libtommath/tommath.pdf) – President James K. Polk Jul 15 '17 at 12:15
  • @John Coleman. Ok i guess I understand now. I dont care about efficiency meaning I dont care if it takes 1s or 10s seconds but everything above that is really slow. For all I know what you suggestested would take insane amount of time for division by smaller numbers (100 digits / 30 digits for example) right? – honzaik Jul 15 '17 at 12:27
  • Binary search will be tolerably quick for what seems to be your purposes. A fraction of a second for numbers of that magnitude (assuming that your multiplication, division by 2, and comparison functions are quick). It is `O(log(n))` where `n` is the number of digits. Having said that, it isn't *that* hard to implement a much better solution. – John Coleman Jul 15 '17 at 12:56
  • @JohnColeman ok, i will look into it. thank you! – honzaik Jul 15 '17 at 13:15
  • You can implement MR without division, if you make your multiplication do the modulo reduction as it goes along (this also prevents the result from being the double the size it needs to be). – harold Jul 15 '17 at 13:46
  • It won't probably run unmodified, but take a look at my [BigInteger code](https://github.com/rvelthuis/BigNumbers/blob/master/Source/Velthuis.BigIntegers.pas) for Delphi. Especially look at the `ModPow()` and `Pow()` methods. – Rudy Velthuis Jul 15 '17 at 16:49
  • Also take a look at Knuth's division code. And you can always do what you have learned in school, especially if you already store the number as digits. – Rudy Velthuis Jul 15 '17 at 16:53
  • @harold: But that modulo reduction does usually require division. Any method that doesn't would be overly complex, IMO. – Rudy Velthuis Jul 15 '17 at 16:57
  • @RudyVelthuis if there actually was a full modulo yes, but my point is it can be avoided entirely, by applying the reduction while multiplying (instead of at the end, when the product has already become big). With binary multiplication it can be just a conditional subtraction, and with base 10 it could still be a variant of that that tries to subtract various multiples.. it's not as nice, but simple – harold Jul 15 '17 at 17:00
  • 1
    @harold: Even in base 10, if numbers reach 200 digits (or even just 30 digits), repeated extraction can become very slow. I already linked to my BigInteger code, which uses base 2^32, but the same principles apply. A basecase division (as described by Knuth, IIRC that is algorithm D in volume 2, but I could be wrong about that) is not terribly complicated, especially not in base 10. – Rudy Velthuis Jul 15 '17 at 17:32
  • FWIW, also take a look at the `divmnu.c` file that can be found on the webs. It implements Knuth's algorithm with half-words (16 bit instead of 32 bit) to avoid any overflows and to make carry detection easier, but that can be done with single digits too. Carry detection should be *much* easier there. – Rudy Velthuis Jul 15 '17 at 17:34
  • @RudyVelthuis can it really get slow, I mean it is at most 10 (or is it 9?) steps right – harold Jul 15 '17 at 17:48
  • @harold: For one digit, yes. Not for numbers consisting of 30 digits. Or I don't quite understand what you mean. – Rudy Velthuis Jul 15 '17 at 17:52
  • @RudyVelthuis I think you're still talking about doing a full modulo *after* the multiplication, but what I'm talking about is reducing *during* the multiplication, so no number ever becomes greater than the base times the divisor. Like modexp, but change the multiplications to additions and you get modmul. – harold Jul 15 '17 at 17:57
  • @JohnColean thank you very much, I have successfully implemeted the algorithm you suggested but sadly overall my modular exponentiation is too slow for larger numbers, not sure where is the biggest flaw but i will look into it. nonetheless it is what i expected and wanted it to be! – honzaik Jul 16 '17 at 18:28

2 Answers2

1

Read this answer for fast multiplication and this page for slower but easier to understand multiplication. Read this page for fast division using that multiplication algorithm. The time complexity will be proportional to the time complexity of the multiplication.

cdo256
  • 973
  • 1
  • 11
  • 16
  • 1
    Note that Fürer's algorithm, Toom-Cook, Schönhage-Strassen, other FFT-based algorithms and even the relatively simple Karatsuba are only faster for **very** large numbers. They have quite some overhead that only becomes negligible for huge numbers, far larger than only 200 digits. That is when the actual time complexity actually comes to play. A simple schoolbook (or basecase or "long") multiplication is much better suited for such 200 digit (or 30 digit) numbers. – Rudy Velthuis Jul 15 '17 at 18:02
0

thank you all for your responses. i have decided to use divison using binary search as suggested here Division (modulus) of large integers (max 200 digits) i realized its not probably what i want because overall my modular exponentiation is slow for larger numbers (60+digits) but the algorithm is pretty simple

honzaik
  • 273
  • 1
  • 10