If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Computer science theory

### Course: Computer science theory>Unit 2

Lesson 7: Randomized algorithms

# Randomized algorithms (intro)

How could random numbers speed up a decision algorithm? Created by Brit Cruise.

## Want to join the conversation?

• As n grows, primes become less and less common. Eventually, could you reach a point that there are no more primes?
• if we did have a finite number of primes then we would not have an infinite number of numbers because you would need primes to make more numbers
• At , we just need to be 99.9999999999999% sure that it's a prime. So, if we have an error and actually get that 1.0e-15 chance that it's not a prime number, going back to RSA, how does this unprime number weaken the encryption? would it mess up the encrypted message itself? how to exploit this leak?
• If p or q is not prime it breaks the RSA algorithm, since it is based on p and q being prime, so that we can choose e and d properly to encrypt and decrypt messages.

What will happen is:
-you will encrypt some plain text M using the public key e to get a cipher text C
-the person will decrypt C using the private key d to get a plain text M'
-M and M' probably won't be the same

Why does this happen?

RSA relies on properties of Fermat's little theorem,or Eulers theorem, both of which assumes p and q are prime.

M mod n= C^e mod n
C mod n= M^d mod n

M mod n= (M'^d mod n)^e mod n = (M'^d)^e mod n = M'^(e * d) mod n

If p,q are prime, Fermat's Little Theorem (or Euler's Theorem) can be used to show us that M'^ (e * d) mod n = M' mod n.
(I've excluded the gory math details, but they also rely on how we chose e and d)
If p and q are not both prime, the value M'^ (e * d) mod n will likely not be M' mod n.

Let's suppose, for a moment, that RSA still worked even though we chose p as a composite.
Having p as a composite would mean we had, at least, two factors >1 for p.
This means we have, at least, 3 factors for n now.
If we had only two factors the largest that the smallest factor could be is the square root of n.
Now, with 3 factors, the largest that the smallest factor could be is the cubed root of n, which is much smaller.
This would make a brute force attack to factor n much easier. (factoring n can be used to reveal the private key)

Hope this makes sense
• Are there "primes and composites" in negative numbers?
• No. By definition, only integers >1 are Prime or Composite.
• There is this theorem called Fermat's theorem, which tests for primes.

Fermat's theorem states that if p is prime and 1 is less than or equal to a which is less than p, then
a^p-1 (mod sign) 1 (mod p)
If we want to test if p is prime, then we can pick random a's in the interval and see if the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probable prime.
It might be in our tests that we do not pick any value for a such that the equality fails. Any a such that
a^n-1 (mod sign) 1 (mod n)

when n is composite is known as a Fermat liar. Vice versa, in this case n is called Fermat pseudoprime to base a.
If we do pick an a such that
a^n-1 (mod sign with a slash through it) 1 (mod n)
then a is known as a Fermat witness for the compositeness of n.

Thanks to Wikipedia!
• Not to cause any confusion, I believe that bkalisetti007 is referring to Fermat's Little Theorem
• can we see visual lecture on any other site? here at pakistan youtube is ban from government
• How are random numbers actually generated?
• That assumes your dice are perfect. Over millions of dice rolls, you would find some numbers are more common than others because tiny imperfections in your dice would result in them favoring one instead of six, or two instead of five. The more you used this method, the more obvious that bias would become.
• What is the chance that I win the lottery twice in a row? Isn't it less likely that I win it twice in a raw than just twice at any two of the weekly draws? And isn't it less likely than just winning the first one and a 1:2 chance of winning the second one? I think the calculation is wrong in the beginning on the video, but I am not sure.
• It's the same as rolling a dice twice in a row. Let's say winning lottery = rolling a 6. Rolling two sixes at the same time, or one six followed by another six is the same: 1/6*1/6 = 1/36.
It doesn't really matter how much time is in-between draws (or rolls)

However, if you are asking about the probability of winning twice over many draws (say inside of a year), then yes that is a different question (and more likely)
• that machine said that if a number isn't expressible in the form 6k+/-1, it's 100% proof that the number is a composite but 2 and 3 can't be expressed in that form and they're primes. So is this little test still proof of composites?
• The 6k+/1 test only works for integers greater than 3, because 2 and 3 are the primes that the test is based upon. But yes, it does work for every prime greater than 3.
(1 vote)
• How does odds of hitting lottery twice in the row is 6 * 10^-14, can anybody explain me?
(1 vote)
• Probability of winning the 6/49 lottery once is:
1/(49 C 6)
where:
49 C 6 is the number of ways we can choose 6 items from 49 (order doesn't matter).
49 C 6 = 49!/(43! * 6!) = 13,983,816
So, the odds of winning once is : 1/13,983,816

Winning the lotto twice (assuming the events are independent) is :
1/13,983,816 * 1/13,983,816 = 1/195,547,109,921,856 ~= 5 * 10^-15

So, 6 * 10^-14 appears to be off a little.
• I got lost at the 6k +/- 1. No idea where that came from
• Prime numbers are in the form 6k+1 or 6k-1 where k is some integer. (But not all numbers in this form are necessarily prime).

Why ?
All integers, are in one of these forms:
6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5
(This is a result of the quotient remainder theorem that states: Given any integer A, and a positive integer B, there exist unique integers Q and R such that A = B * Q + R where 0 ≤ R < B )
Numbers of the form:
6k are divisible by 6 thus not prime
6k + 2 = 2 * (3k+1) so divisible by 2 thus not prime
6k + 3 = 3 * (2k+1) so divisible by 3 thus not prime
6k + 4 = 2 * (3k+2) so divisible by 2 thus not prime
Which leave us with:
6k+1, 6k+5 being potentially prime
6k-1 is equivalent to 6k+5 because we can use the next higher k as follows: 6(k-1)+5= 6k-1
e.g. 17 = 6 * 2 + 5 = 6 * 3 - 1
(Or we could just say because -1 mod 6 = 5)
So we can just use 6k +/- 1

Hope this makes sense