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