0

I am trying to implement RSA crypto system using some equations to get better time for decryption. The problem that I have is a huge numbers in the function that calculate "n choose k", the factorial for huge numbers take a lot of time. When I start wrote the code I wrote it with naive calculation, but now I am seeing that the program running time very long, even if I compare to the original RSA. Also I use in GMP library for big numbers, but it doesn't affecting on the problem, I hope.

Jarod42
  • 203,559
  • 14
  • 181
  • 302
Roni Belkin
  • 1
  • 2
  • 1
    If you only need an approximate values you can use gamma functions. Otherwise make sure you cancel out as much as possible in n!/((n-k)!k!) – PiRocks Apr 27 '20 at 18:17
  • No, I must calculate it, the "n choose k" , is for encryption and also in decryption, if I will use approximate values, the encryption and decryption will not work. If I cancel as much I can, does it the best way to get best efficient ? – Roni Belkin Apr 27 '20 at 18:24
  • How large are n and k? – ALX23z Apr 27 '20 at 18:29
  • 3
    IIRC textbook RSA does not use the binomial coefficient. As far as I know if you need exact integer values canceling out is the most efficient option. – PiRocks Apr 27 '20 at 18:30
  • 1
    There may be faster ways of computing (nCk mod m) , but that probably belongs on mathematics stack exchange – PiRocks Apr 27 '20 at 18:31
  • Why the C tag if you're looking for a C++ solution? – jwdonahue Apr 27 '20 at 18:36
  • formula `n!/((n-k)!k!)` is only like that for mathematical convenience. Implementing that literally is very inefficient. Canecelling out terms as much as possible is the way to go. For what range of `n` and `k` do you need the result? Perhaps precomputing them and keeping a table is viable. Are `n` and `k` known at compile time? Then you could rely on compile-time computations – 463035818_is_not_an_ai Apr 27 '20 at 18:39
  • n can be 20 digits, also k. I trying to implement RSA using Rèdei rational functions. – Roni Belkin Apr 27 '20 at 18:39
  • @RoniBelkin Factorials grow very fast, so you'll need to either use an arbitrary precision library, or use *some* approximation (and prove that it doesn't affect the final result when you convert back to an integer type). See for example [1](https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations), [2](https://stackoverflow.com/questions/14556266/how-to-calculate-combination-of-large-numbers), [3](https://stackoverflow.com/questions/12983731/algorithm-for-calculating-binomial-coefficient). – dxiv Apr 27 '20 at 20:48
  • 20 digits? 10^20? You realize that even storing "n choose k" requires over a megabyte of data. Even if you knew `n!, k!, (n-k)!` it would take unreasonable amount of time just to compute the division. I am not sure what kind of cryptography you want to implememt but you surely do something very wrong. – ALX23z Apr 27 '20 at 21:34
  • Edit: my bad, not megabytes but rather about as much bytes as n~ 10^20 - which beyond what a super computer can store on a harddrive. You definitely do something very wrong. – ALX23z Apr 27 '20 at 21:47
  • 2^68 for example works, all what I wrote it power with base of 2. It works, but it take a lot of time. – Roni Belkin Apr 28 '20 at 19:42
  • @RoniBelkin no you cannot compute, say "2^68 over 2^67", as this number you cannot store on the computer in any way of form. And having million years of wait for computation is also not considered "works". If by "20 digits" you meant 2^20 - please communicate as normal people do - as this is just 10^6 for which it is a very different story. – ALX23z Apr 29 '20 at 22:58

1 Answers1

0

Using Pascal's triangle is a fast method for calculating n choose k. You can refer to the answer here for more info.

The fastest method I know of would be to make use of the results from "On the Complexity of Calculating Factorials". Just calculate all 3 factorials, then perform the two division operations, each with complexity M(n logn).

Quantum Guy 123
  • 148
  • 8