-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.