-module(halting_problem). -import(lists,[seq/2]). % gcd g(A,0) -> A; g(A,B) -> g(B, A rem B). % power p(_,0) -> 1; p(A,B) -> A * p(A,B-1). % If A^R = 1 mod N and R is even, then % (A^(R/2)-1)(A^(R/2)+1) is divisible by N. % If A^(R/2) is not 1 or -1 mod N, then we have % found a nontrivial factor of N. If so, tell % the main process about it. If not, return % quietly. % % Shor's algorithm uses this procedure. However, % Shor's algorithm uses a quantum computer to find % good values for a and r in a reasonable amount % of time, while this program spawns over 10^400 % processes in order to try every possibility. f(A,R,N,F) -> P = p(A, R div 2) rem N, Q = p(A, R) rem N, if R rem 2 == 1 -> ok; Q /=1 -> ok; P == N-1 -> ok; P == 1 -> ok; true -> F ! min(g(P-1,N),g(P+1,N)) end, ok. d(S,N) -> [ spawn(fun() -> f(A,R,N,S) end) || A <- seq(2,N-2), R <- seq(1,N-1) ]. % Finds the smaller of the two prime factors of the large number shown % below. This number is RSA-768, and its smallest prime factor is % 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489. main(_) -> S = self(), spawn(fun() -> d(S,1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413) end), receive X -> io:format("~p~n",[X]) end.