The above paper solves the discrete logarithm in time O(N^3) not O(n^3), two very different things. N being the size of the modulus, n being log_2 of N (the binary length). There are many algorithms that will solve the discrete log problem much faster than this method, brute force search runs at a worst case of O(N), or in other words O(2^n). The provided algorithm in the above paper runs in (2^(3*n)).
login/create account
Drupal
CSI of Charles University
N != n
The above paper solves the discrete logarithm in time O(N^3) not O(n^3), two very different things. N being the size of the modulus, n being log_2 of N (the binary length). There are many algorithms that will solve the discrete log problem much faster than this method, brute force search runs at a worst case of O(N), or in other words O(2^n). The provided algorithm in the above paper runs in (2^(3*n)).