Kongruenssiyhtalo2.jl

# Kongruenssiyhtälön 2^(n-2) = 1 (mod n) ratkaisut
using Primes

function factors(n)
    f = [one(n)]
    for (p,e) in factor(n)
        f = reduce(vcat, [f*p^j for j in 1:e], init=f)
    end
    return length(f) == 1 ? [one(n), n] : sort!(f)
end

function multorder(a, m)
    gcd(a,m) == 1 || error("$a and $m are not coprime")
    res = one(m)
    for (p,e) in factor(m)
        m = p^e
        t = div(m, p) * (p-1)
        for f in factors(t)
            if powermod(a, f, m) == 1
                res = lcm(res, f)
                break
            end
        end
    end
    return res
end
# multiplicative order of 2 modulo primes
b= primes(1,1000000);
max = length(b);

function sopivat_alkuluvut(max)
    properprimes = Int64[]  # kongruenssiyhtälölle kelvolliset kanditaatit
    # multorder(2,p) pariton ja p jaettuna 8:lla antaa jakojäännöksen 1 tai 7
    s = 0
    for i in 2 : max
        if multorder(2,b[i]) % 2 != 0 && (b[i] % 8 == 1 || b[i] % 8 == 7)
            #println(b[i])
            s += 1
            push!(properprimes,b[i])
        end
    end
    println("sopivia alkulukuja oli ",s)
    return properprimes
end
# testaan kelvollisilla alkulukukanditaateilla p kongruenssiyhtälö
# testataan n = q*p =(k*ord(2,p))+2)*p yhtälölle 2^(n-2) = 1 (mod n)
properprimes = sopivat_alkuluvut(max);
nnumbers = Int64[]
nmaxproper =length(properprimes)
half1 = div(nmaxproper,2)+1  # alkulukujen puoliväli
half2 = half1-1   # toinen puolisko
# lasketaan ensin suurimpien alkulukutekiojöiden avulla
# näin saadaan sisäsilmukan k:t pieniksi
for i in nmaxproper : -1 : half1      # aloitetaan suurimmista alkuluvuista
    mult = multorder(2,properprimes[i])
    for k in 1 : 2: 100000
        n = (k*mult+2)*properprimes[i]
        if powermod(2,n-2,n)==1
            #println(n," factors: ",factor(n))
            push!(nnumbers,n)
        end
    end
end
for i in half2 : -1 : 1  # jatketaan puolivalista alkuun
    mult = multorder(2,properprimes[i])
    for k in 1 : 2: 100000
        n = (k*mult+2)*properprimes[i]
        if powermod(2,n-2,n)==1
            #println(n," factors: ",factor(n))
            push!(nnumbers,n)
        end
    end
end

nsorted = sort(nnumbers);
nlukuja = length(nsorted)
for i in 1 : nlukuja
    println(nsorted[i],"  ",factor(nsorted[i]))
end
# poistetaan n-tuloslistan toistot
# puhdistettu lista nlukujavalmis
nlukujavalmis = Int64[nsorted[1]]
for i in 1 : nlukuja-1
    if nsorted[i] != nsorted[i+1]
        push!(nlukujavalmis,nsorted[i+1])
    end
end
nlukuja_valmis = length(nlukujavalmis);
# tulostetaan valmiiden lista
for i in 1 : length(nlukujavalmis)
    println(i,"  ",nlukujavalmis[i],"  ",factor(nlukujavalmis[i]))
end