0 like 0 dislike
0 like 0 dislike
Time Complexity of Miller Rabin Algorithm

1 Answer

0 like 0 dislike
0 like 0 dislike
The short answer is, log n is the number of digits of n. So it will keeps coming up, because a lot of operations has length proportional to the digits of n.

r is O(log n). d is O(n).

Initial factoring of n into 2^r d is O(log n), because its run time is proportional to r.

Raising to power of d modulo n takes O(log d) multiplication operations using exponentiation by squaring, which is within O(log n). Each multiplication multiply 2 numbers with at most O(log n) bits and a modulo operation between a number with at most O(log n) bits and n. Each takes O(log^2 n) using naive school book's algorithm (but can certainly be done faster). So you have total of O(log^3 n) number of operations.

The loop inside run at most r times, so it runs at most O(log n) times. Each run of the loop take O(log^2 n) operations using the same argument as above (naive school book's algorithm), for a total of O(log^3 n).

So total is O(log^3 n).

You can certainly improve this bound if you don't use naive school book algorithm. I believe the state of the art research will get you O(log^2 n log log n).

Related questions

0 like 0 dislike
0 like 0 dislike
3 answers
RashidAbdalla asked Jun 21
[The article](https://www.reddit.com/r/statistics/comments/vh2ecs/analysis_of_russian_vaccine_results_suggests_they/) [Twitter summary](https://twitter.com/K_Sheldrick/st...
RashidAbdalla asked Jun 21
0 like 0 dislike
0 like 0 dislike
1 answer
MSR_Tlse asked Jun 21
Are the S3/S4 Edexcel Further Maths units useful to become an actuary? Topics include sampling, unbiased and biased estimators, confidence intervals and significance test...
MSR_Tlse asked Jun 21
0 like 0 dislike
0 like 0 dislike
20 answers
balkissoon asked Jun 21
Considering leaving the actuarial profession. What are some interesting fields you've heard of former actuaries going into? How did they get into the new field?
balkissoon asked Jun 21
0 like 0 dislike
0 like 0 dislike
9 answers
HilaryKHarper asked Jun 21
Has anyone successfully guessed on like half of the questions on an exam and still passed?
HilaryKHarper asked Jun 21
0 like 0 dislike
0 like 0 dislike
0 answers
RyanWCTV asked Jun 21
Range of two Discrete Random Variables
RyanWCTV asked Jun 21

33.4k questions

135k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!