Article By: En-Jui Kuo
What is a prime number?
In elementary school, we all know that the definition of prime numbers: A positive integer greater than one and it can't not be factorized into two integers both greater than one.A natural number greater than 1 that is not prime is called a composite number. Prime number :2, 3, 5, 7, 11, 13,.....
Old story
Ancient Greek mathematics Euclid already knew that there are infinite prime numbers and any composite number can be factorized into a product of primes uniquely(up to their order). But how can we factorize a composite number in practice?a simplest way
A simplest way is that we first prepare a list of primes: 2,3,5,..... . When you give me a composite number, then I test which primes can divide that composite number. For example, we want to factor 91, then we find 91 is divisible by 7. Then we use same algorithm on quotient until quotient is 1. So we find$$ 91=13*7 $$
Theorem 1
A number N is composite number if it is divisible by a prime number which is smaller or equal to $$\sqrt{N}$$ Proof:Suppose N can be factor into two numbers (NOT 1*N OR N*1): We can write $$N=a*b$$ Then either one of them is divisible by prime number which is smaller or equal to $$\sqrt{N}$$. Otherwise if both can not be factorized then:
$$a>\sqrt{N}, b>\sqrt{N}$$ then a*b> N.
We lead to a contradiction.
So if we want to factorized a composite number we need to prepare a list of primes smaller or equal to $$\sqrt{N}$$. Let $$\pi(x)$$ (called prime-counting function)denoted a function that gives the number of primes less than or equal to x. For example: $$\pi(10)=4 , \pi(11)=5$$. Since 2,3,5,7 are primes lower than 10 etc.
We have a bad news below:
Theorem 2: Prime Number Theorem
Roughly speaking(ln(x) means natural log): $$\pi(x) \approx \frac{x}{ln(x)} $$ So if you want to factorize a number which has 100 digits, there are approximately 10^97 primes since $$\pi(10^{100}) \approx \frac{10^{100}}{ln(10^{100})} \approx 4.34294\times 10^{97}$$. There is no hope to factorize this kind of large numbers using this stupid way. By the way, Prime Number Theorem is not easy to proof. There are famous conjectures related to prime-counting function which are not solved until now. You can see Prime-counting_function and Second Hardy–Littlewood conjecture The error term is related to a problem belonging to seven millennium prize problems called Riemann Hypothesis. I am very interested in this topics.Order finding Algorithm
Theorem 3
Given an natural number a greater than 1 and coprime to N. Then there is an natural number x (called order) such that: $$a^{x}=1(\mathrm{mod} N)$$ proof: Simple group theory: $$ \text{consider } a^{1}(\mathrm{mod} N), a^{2}(\mathrm{mod} N),...a^{N}(\mathrm{mod} N), $$ We only have N-1 possibilities in the reminder (0 is impossible since a is coprime to N): But we have N values. So two of them are equal said $$\alpha ,\beta$$ such that $$ a^{\alpha}(\mathrm{mod} N) = a^{\beta}(\mathrm{mod} N) \text { lead to } a^{\alpha-\beta}=1 (\mathrm{mod} N))$$. We finish the proof.Besides, we can find smallest natural number x which satisfy the equation. Since natural number has a lower bound 1.
By this theorem, we have an algorithm. pick any a which is coprime to N. We can find this x. If x is an even number then $$a^{x}= 1(\mathrm{mod} N)$$ so $$(a^{x/2}-1)(a^{x/2}+1)=0(\mathrm{mod} N)$$ There's a chance $$gcd(a^{x/2}-1, N) \text{, (gcd means the great common divisor)}$$ is not 1 or N.
Example
There is an example below using python: Suppose we want to factorize 606858167: pick a=2, first we can use brute force to find order: we find $$2^{50567308}=1 (\mathrm{mod} 606858167)$$ then we find: $$gcd(2^{\frac{50567308}{2}}-1, 606858167)=19759$$ Finally we get $$606858167=19759*30713$$ Both of them are large primes.
More fancy way factoting large integer?
Yes, we have quantum algorithm called Shor's algorithm. I will spend a small paragraph trying to explain this idea.quantum computing
the difference of quantum computing and classical computing is that classical bit can be changed to vector $$ |0>, |1> $$ one can see this lies on complex planes: and a bit can exhibit on the superposition state $$ a|0> +b|1> $$. which a, b can be complex number. So you can think that quantum computer is like some algorithm and devices which can manipulate the quantum states and finally measure the quantum state which could give us the answer. but giving a successful quantum algorithm is not so easy since measuring states will cause the state to the eigenstate of that measurement. Suppose we have a state in our hand called $$\phi= a|0>+b|1>$$ and we don't know the coefficient. If we measure it, it will have some chance becoming state 0 or state 1 then we lost our coefficient a and b.Tensor product
It is hard to explain the math detail here. But we can view tensor means different place in the biniary place. i,e we view: $$01 \to |0 > ;\mathop{\otimes}|1> ; $$ a computing means that we can construct some black box (function f)can manipulate state: $$ |x>|y> \to_{f} |x>|y+f(x)> $$. Now, we can start to illustrate this idea:shor algorithm
first, we pick up a number called "a" before. then now we have quantum computing:- create the superposition state $$ \frac{1}{\sqrt{2^n}}\sum_{0}^{2^n-1}|x> |0> $$
- suppose we have an operator satisfy $$ f|x> |y> \to |x> |a^x+ y(mod N)>$$ , so now, we have $$ f \frac{1}{\sqrt{2^n}}\sum_{0}^{2^n-1}|x> |0>= \frac{1}{\sqrt{2^n}}\sum_{0}^{2^n-1}|x>|a^x(mod N)>$$ so actually if n is greater enough, the order must include in some $$ |a^x(mod N)>$$ then we measure the second qubit, suppose r=order, then we have $$|x0>+|x0+r>+|x0+2r>+|x0+3r>.... ...$$ I drop the normalization factor now. Finally, it seems like we are done since we can read the coefficient in the state to get our order and apply the order finding algorithm to solve this problem. However this is not true since we can not know the answer until we measure it. Finally, we need a devices called quantum fourier transform which can be seen at Quantum Fourier transform to extract the number.
No comments:
Post a Comment