Is this time normal or there is faster algorithm? I used trivial search for primes p and q, solved k1*p+k2*q=1 by analog of Euqlid algorithm and assume idemponets are 0, 1, k1*p (where k1*p is positive) and n+1-k1*p.

can you explain why you do that?