A&DS S04E10. Number Theory Algorithms

Algorithms and data structures. Semester 4. Lecture 10.
In this lecture we talked about basic number theory algorithms: primality testing, factorization, greatest common divisor, diophantine equations, and the chinese remainders theorem.
ITMO University, 2022

[@bovelles8275]

You are be the best keep it up plz❤️

[@tiwerlol6914]

is a lecture about combinatorics coming?

[@ayushgangwani1359]

nice explanation also cool t shirt 😆

[@madhukiranattivilli2321]

15:00 -- gcd(a,b) = gcd(b, a%b) Hi Pavel, Is the below what u said about a%b where they are huge numbers? a%b = a - ⌊a/b⌋b Assuming worst case scenario for a%b, i.e. a & b far away from each other -- i.e. a,b = O(n), O(1) We add b to itself O(n) times, and then subtract the result from a Each addition of big numbers in O(logn) time O(n) additions in O(nlogn) time Subtraction in O(logn) time Hence T(a%b) = O(nlogn) Am I correct?

[@madhukiranattivilli2321]

Fourth root algo, Hi Pavel, Since gcd(a, b) can return a composite number, and since we want gcd() to return a prime factor, I think your "Fourth Root Algo" is best suited to check if a number is prime or not, instead of prime factorization. Makes sense?

[@pavelmavrin]

to check the primality you can use the much faster methods

[@madhukiranattivilli2321]

@1:10:00 -- Miller-Rabin test Hi Pavel, Is this the modification to "Fermat test" algo? miller_rabin_is_prime(n) : if (n == 2) return true if (n is even) return false a = random(2…n-1) x = n-1 loop : if fermat_test_is_prime(a, x, n) is false return false if x is odd break x >> 1 endloop return true fermat_test_is_prime(a, x, n) is same as ur isPrime(n) : if gcd(a, n) ≠ 1 return false if aˆx %n ≠ 1 return false return true

[@pavelmavrin]

yes

[@madhukiranattivilli2321]

Time complexity of isPrime(n) algos Hi Pavel, Is it correct to say Fermat Test algo runs in O(logn) and Miller-Rabin Test algo runs in O(log²n)?

[@pavelmavrin]

not exactly, since the arithmetic operations on long integers are not O(1), the time complexity of both Fermat and Miller-Rabin tests is something like O(log^3 n)

[@madhukiranattivilli2321]

Miller-Rabin Test algo to check for prime number Hi Pavel, You spoke about Fermat Test algo declaring a composite number as a prime number sometimes, and hence you enhanced it as the Miller-Rabin Test algo However, I noticed that 61 is a prime number. But for certain values of a⟘61 like 5, 40, etc… 61 is declared as a composite number! 5⁶⁰%61 = 1 5³⁰%61 = 1 5¹⁵%61 = 60 This is problem #1 Problem #2 : The popular isPrime(n) algo that tests with odd factors upto √n runs in O(√n) time, whereas this Miller-Rabin Test algo runs in O(log²n) time -- O(logn) for each Fermat-Test algo run. And, O(logn) times we call Fermat-Test algo -- considering the worst case situation of n-1 being a power of 2 (ex: n=1025, call Fermat-Test algo 10 times). O(√n) is definitely better performance than O(log²n). So, effectively the basic isPrime() algo seems to be the best approach! Could you please comment on this? Did I make some mistake anywhere?

[@pavelmavrin]

1) 60 = -1 modulo 61, so it will pass 2) no, O(√n) is much slower than O(log²n). remember we are talking about huge numbers here, like n=2^1024

[@madhukiranattivilli2321]

isPrime(n) :: Miller-Robin Test algo Hi Pavel, I think I understood how the probability can be increased from 75% to 100%. Could you please review this and confirm/comment? U said a^k %n = j for some k = y*2^x where 1 < j < n y : odd integer and a^(2x) %n = 1 So, (j+1 * j-1) %n = 0 Since j can not be ±1, u said n is prime I didn't understand ur logic, so I explored a little more, and I found the following : If n is prime : n has to be a factor of either j+1 or j-1, coz the remainder has to be 0. But 1 < j < n. So, max value of j is n-1. So, max value of j+1 is n, and max value of j-1 is n-2. So, n can be a factor of only j+1. So, when n is prime, if j > 1, j has to be n-1, which is same as -1, coz -1 %n = (-1 + n - n) %n = n-1 If n is composite : n can have atleast 2 factors. Let n = x*y. Now, either n or x or y can be factors of j+1 or j-1 or (j+1 * j-1). But, n can not be a factor of j-1 for the reason I wrote above. Hence, 3 possibilities : (1) fermat test return code = 1 try with exponent = k/2 (2) return code = n-1 indecisive -- can be a prime or a composite so, try with another value of a, 1 < a < n, and exponent = n-1 (3) 1 < return code < n-1 n is a composite number Hence, for normal sized numbers, we add an additional O(n) factor to handle case#2 (i.e. resolve the conflict b/w prime or composite). And O(logn) iterations of case#1. And O(logn) time for the fermat test. Hence O(nlog²n) time for small numbers, and O(n²log³n) time for very large numbers (due to O(nlogn) time to perform x%y (i.e. remainder) OPs) Please lemme know if I made a mistake anywhere.

[@pavelmavrin]

I don't get it. How is it 100% if it never says that N is 100% prime?

[@madhukiranattivilli2321]

@1:29:45 -- # of prime factors of a number Hi Pavel, U said a number wud have no more than logn prime factors Isn't it √n prime factors?

[@pavelmavrin]

no, since N is a product of these numbers, and they all are >= 2, there is no more than log n of them

[@madhukiranattivilli2321]

Fourth Root Algo Hi Pavel, I've implemented this. Works great. But a slight hiccup. gcd(X2i - Xi, n) sometimes would be a composite number -- like 21, when 3 and 4 are two of few prime factors of n I think, instead of gcd() we should compute a_common_divisor(X2i - Xi, n) -- this wud stop after 3 is found, and wouldn't again proceed to find 7 also. 7 will be found in a later iteration Is this good enough?

[@pavelmavrin]

If you manage to find any composite divisor of N, you can apply the same algorithm to it, and split it into smaller divisors, until you get prime numbers

[@madhukiranattivilli2321]

@1:01:30 -- isPrime(n) Hi Pavel, (1) Yi = Xi * a (2) if (an-1 ≠ 1) return false Did u imply (an-1 %n) and (Xi * a) %n ?

[@pavelmavrin]

I don't get it. These two lines are from different parts

[@madhukiranattivilli2321]

@@pavelmavrin yes from different parts. Question is about the implied %n I think u implied it. Felt so after watching entire video

[@pavelmavrin]

@@madhukiranattivilli2321 oh yes, i omit %n everywhere

[@kxb6098]

5:25 expression is wrong, it should be gcd(a, b) = gcd(b, a%b)

[@pavelmavrin]

Yes sure