random curve with point

If you just need any short form weierstrass curve at random with a random point the easiest way is to create the point first, then the curve.
suitable for lenstra.
Given a composite you would like to factor.
toy example:
given N= 1289
random point P=(x,y)=(235,156)
random A= 21
calculate B as
B=y^2 -x^3 - A*x mod N
156^2-235^3-21*235 mod 1289 gives B=-157
then you got your random curve:
Y^2=X^3 + 21X-157 with a point P that by construction is on the curve.

the solution for B ofcourse can be plus/minus any multiplication of N. equivalence class: B + Z/ZN
More about lenstra later

Double and Add algorithm

Very much like the fast powering algorithm - binary expansion can be used to calculate Q= nP fast.
ex n=947 = 2^9+2^8+2^7+2^5+2^4+2^1+2^0

which means that 947P = P+2P+16P+32P+128P+256P+512P. Thats 9 doublings and 6 additions, much better than 946 additions....
if we allow subtraction as well (ternary expansion) its even better.

want to calculate nP?

algorithm:

1. input point P from E(Fp) and n>=1
2. set Q=P and R=Ø (point at infinity)
3. loop while n>0{
     if n = 1 (mod2) set R= R+Q
     set Q=2Q and n=n/2 (floor)}
4.return R (which equals nP)

I've now posted working sourcecode available at http://christelbach.com
(source code contained in master thesis)

for instance this:
//double and add algorithm

private BigInteger[] calculatenP(BigInteger x, BigInteger y, BigInteger n, BigInteger A, BigInteger modp)
{
BigInteger[] Q = { x, y };
BigInteger[] R = { 0, 0 };
while (n > 0)
{
   BigInteger t = BigInteger.ModPow(n, 1, 2); 
   if ((t) == 1)
   {
   R = addPoints(Q[0], Q[1], R[0], R[1], modp);
   } 
   Q = doublePoints(Q[0], Q[1], A, modp);
   n = n / 2;
}
BigInteger[] resPoint = { R[0], R[1] };
return resPoint;
}

Look in the pdf file for the methods addPoints() and doublePoints()

square roots modulus

IF a has a square root modulus p,we can solve it like this:

we have x^2= a mod p, then
b= a^((p+1)/4)mod p
will be a solution. It will satisfy b^2=a mod p.
Isn't that a miracle!

Remember ONLY if a has a squareroot mod p...that certainly not allways the case.

more inverse

how could I forget fermat's little..
a^(p-1) = 1 mod p if p does not devide a, and 0 otherwise.
Multiply a^(p-2) with a and we will get:

a^(-1)= a^(p-2) mod p


together with fast powering algorithm this is handy and to some limit efficient!
An alternativ to the euclidian algorithm.

About fast powering algorithm:

toy example

5^11 mod 13
write 11 as a sum of power of 2 (like binary)
11= 1011, which means 11= 5^(2^3+2^1+2^0)= 5^(2^3)*5^2*5. Reduce mod 13 in each step and the numbers will stay low
so the result is 1*12*5= 60 mod 13= 8

In general:
create a table with relevant powers mod p to some limit, The easy part is that each number is just the square of the preceding one.