final -- Sage

### finds an appropriate prime p given the cardinality of the sought curve N ### ### optional argument p --- the last p that was found, and for some reason discarded further in the algorithm ### def find_prime( N, p = None ): p_max = N + 1 + ZZ( floor( 2*sqrt(N) ) ) p_min = N + 1 - ZZ( floor( 2*sqrt(N) ) ) if p == None: p = p_min - 1 while true: if p == N+1: raise ArithmeticError("Finished search for primes, probably we are unable to find the curve because of insufficient computational capacity!") if p < N+1: p = p_max - (p - p_min) - 1 else: p = p_min + (p_max - p) if p in Primes(): return p

### tests the function find_prime ### def find_prime_test( fp , silent = true): N_min = 10e6 N_max = 10e7 n_test = 100 for n in range(n_test): N = randint(N_min, N_max) p = fp(N) t = p+1-N fail = (t^2 > 4*p) or (p not in Primes()) if not silent: print "N:", N print "p:", p print "t:", t print "Test passed:", not(fail) print " " if fail: raise ArithmeticError("Test failed!") print "Test passed! Assuming ", fp, "works correctly." find_prime_test(find_prime)

Test passed! Assuming  <function find_prime at 0xa92b10c> works
correctly.

Test passed! Assuming  <function find_prime at 0xa92b10c> works correctly.

### precise numbers, to make computation easier def PReal(digits): bits = ceil(digits*log(10)/log(2)) return RealField(bits) def PComp(digits): bits = ceil(digits*log(10)/log(2)) return ComplexField(bits) ### TEST ### print "Real numbers with a hundret digits:", PReal(100) print "Complex numbers with a hundret digits:", PComp(100)

Real numbers with a hundret digits: Real Field with 333 bits of
precision
Complex numbers with a hundret digits: Complex Field with 333 bits of
precision

Real numbers with a hundret digits: Real Field with 333 bits of precision
Complex numbers with a hundret digits: Complex Field with 333 bits of precision

##### j - invariant related stuff #####

### the q nome ### def q(tau): return exp(2*I*pi*tau)

### the eta invariant ### def eta(tau, digits, silent = true): if tau.imag_part() < 0: raise ArithmeticError("Summing non-convergent series while computing eta") #max_n = 1 #while 2*abs( q(tau*max_n*(3*max_n-1)/2))/(1-abs(q(tau))) > 10^(-digits) : # max_n +=1 max_n = ZZ(ceil( sqrt(( ln(6) + digits*ln(10) )/3*pi*tau.imag_part() ) )) if not silent: print ">Computing eta at argument tau =", tau, "with number of summands max_n =", max_n, "hoping for at least", digits, "correct digits" sum = 1 for n in range(1,max_n+1): sum += (-1)^n*( q(tau*n*(3*n-1)/2) + q(tau*n*(3*n+1)/2) ) sum *= q(tau/24) if not silent: print ">Done computing eta, result is:", sum return sum

### the Delta invariant ### def Delta(tau, digits, silent = true): if not silent: print ">Computing Delta at argument tau =", tau, "hoping for at least", digits, "correct digits" eta_val = eta(tau, digits = digits+5, silent = silent) res = (2*pi)^12* (PComp(digits+5)(eta_val))^24 #res = (2*pi)^12* eta(tau, digits = digits+5)^24 return res

### the j invariant itself ### def f(tau, digits, silent = true): if not silent: print ">Computing f at argument tau =", tau, "hoping for at least", digits, "correct digits" D2 = Delta(2*tau, digits = digits+2, silent = silent) D1 = Delta(tau, digits = digits+2, silent = silent) res = D2/D1 return res def j_inv(tau, digits = 100, silent = true): if not silent: print ">Computing J at argument tau =", tau, "hoping for at least", digits, "correct digits" f_val = f(tau, digits = digits+4, silent = silent) res = (256*f_val + 1)^3/f_val #res = (256*Delta(2*tau,digits+5) + Delta(tau,digits+5))^3/(Delta(tau,digits+5)^2*Delta(2*tau,digits+5)) if not silent: print ">Done computing j, result is:", res return res

### a test to see if the j invariant works correctly, based on a few values borrowed from wiki ### def test_j_inv_wiki( j , digits = 10, silent = true): arg = [I, sqrt(2)*I, 2*I, 2*sqrt(2)*I, 4*I, (1 + 2*I)/2, (1+2*sqrt(2)*I)/3] pre_val = [1, 5/3, 11/2, 5*(19 + 13*sqrt(2))/6, (724+513*sqrt(2))/4, (724-513*sqrt(2))/4, 5*(19 - 13*sqrt(2))/6] val = [1728*x^3 for x in pre_val] err = [ PComp(2*digits)( (j( arg[i], digits ) - (val[i]))/abs(val[i])) for i in range(len(arg))] pas = [ ( abs(err[i]) < 10^(-digits) ) for i in range(len(arg)) ] my_val = [j(x, digits) for x in arg] for i in range(len(arg)): if not silent: print "<<< TEST >>>:" print "Argument: ", arg[i] print "True value: ", val[i] print "Error: ", CC(err[i]) print "Error order:", RR(-log(abs(err[i]))/log(10)) print "Test passed:", pas[i] print "<<< DONE >>>:" if pas[i] == false: raise ArithmeticError("Test of j invariant failed!") print "Test passed! Assuming j invariant works correctly at precision level: digits = ", digits

### a test to see if the j invariant works correctly, based on a few randomly chosen curves ### x,y = var('x,y') def test_j_inv_curve( j , digits = 10, silent = true): min_a = -100; max_a = 100; min_b = -100; max_b = 100; test_number = 100 for test_iter in range(test_number): a = 0; b = 0; while 4*a^3 + 27*b^2 == 0: a = randint(min_a, max_a) b = randint(min_b, max_b) E = EllipticCurve(y^2 == x^3 + a*x + b) Lambda = E.period_lattice() basis = Lambda.normalised_basis(prec = 4*digits) tau = basis[0]/basis[1] if not silent: print "Curve:",E print "tau:", tau j_real = E.j_invariant() j_comp = j(tau, digits = digits, silent = silent) j_err = j_real - j_comp ord_err = CC(log(abs(j_err))/log(10)) pas = simplify( ord_err < -digits/2 ) if not silent: print "<<< TEST >>>:" print "Argument: ", tau print "True value: ", CC(j_real) print "Computed value: ", CC(j_comp) print "Error: ", CC(j_err) print "Error order: ", ord_err print "Test passed: ", pas if pas == false: raise ArithmeticError("Test of j invariant failed!") print "<<< DONE >>>:" print "Test passed! Assuming j invariant works correctly at precision level: digits = ", digits

### run the test ### for d in [10, 20, 30, 40]: test_j_inv_curve(j_inv, digits = d, silent = true)

Test passed! Assuming j invariant works correctly at precision level:
digits =  10
Test passed! Assuming j invariant works correctly at precision level:
digits =  20
Test passed! Assuming j invariant works correctly at precision level:
digits =  30
Test passed! Assuming j invariant works correctly at precision level:
digits =  40

Test passed! Assuming j invariant works correctly at precision level: digits =  10
Test passed! Assuming j invariant works correctly at precision level: digits =  20
Test passed! Assuming j invariant works correctly at precision level: digits =  30
Test passed! Assuming j invariant works correctly at precision level: digits =  40

### run the test ### for d in [10,20,30,40]: test_j_inv_wiki(j_inv, d)

Test passed! Assuming j invariant works correctly at precision level:
digits =  10
Test passed! Assuming j invariant works correctly at precision level:
digits =  20
Test passed! Assuming j invariant works correctly at precision level:
digits =  30
Test passed! Assuming j invariant works correctly at precision level:
digits =  40

Test passed! Assuming j invariant works correctly at precision level: digits =  10
Test passed! Assuming j invariant works correctly at precision level: digits =  20
Test passed! Assuming j invariant works correctly at precision level: digits =  30
Test passed! Assuming j invariant works correctly at precision level: digits =  40

### computing Hilbert class polynomial ### X = var('X') def find_tau( A, B, D ): return (-B + I*sqrt(abs(D)) )/(2*A) ### digits --- the precision of the j-invariants, expressed in decimal digits; if the coefficients don't seem right, we call find_H once again with precision doubled; this avoids mundane computation of the required precision (which would probably only give an upper bound significantly larger than the actual needed precision) and hopefully keeps the (asymptotic) complexity at the right level. def find_H(D, digits = 20, silent = true): max_digits = 400 if digits > max_digits: print "Cannot compute with such precision! Using SAGE's function hilbert_class_polynomial." return hilbert_class_polynomial(D)(X) if not fundamental_discriminant(D): raise ArithmeticError("Wrong argument! Expecting a fundamental discriminant!") R = PComp(digits)[X] H = R(1) max_B = ZZ(floor( sqrt(abs(D)/3) )) B = D % 2 while B <= max_B: T = ZZ( (B^2 - D)/4 ) A = max(1,B) while A^2 <= T : if T % A == 0: C = ZZ(T/A) if A < abs(B) or C < A: raise ArithmeticError("Something wrong in Hilbert polynomial!") tau = find_tau(A,B,D) j_val = j_inv( tau, digits) #print "Computing j-invariant with argument tau=", tau #print "Result is j =", j_val if A == B or A^2 == T or B == 0: H *= R(X) - R(j_val) else: H *= R(X)^2 - R(2*j_val.real_part()*X) + R(j_val.norm()) A += 1 B += 2 if H != R(1): c = H.coeffs() else: c = [[1+0*I,0]] for i in range(len(c)): c_old = c[i] c_new = round( (PComp(digits)(c_old)).real_part()) c_diff = c_old - PComp(digits)(c_new) if abs(c_diff) > 10^(-10): if not silent: print "Dangerously large fractional part while computing coefficients of H_D" print "Fractional part:", c_diff print "Trying to achieve better precision using", 2*digits, "digits" return find_H(D, 2*digits) c[i] = c_new ### For theoretical reasons we know that the constant coefficient is a cube. We use that as an additional test to detect some (unlikely) computational error. if not is_cube(c[0]): if not silent: print "Correction test failed!" print "Trying to achieve better precision using", 2*digits, "digits" return find_H(D, 2*digits) H = sum([ c[i]*X^i for i in range(len(c))]) return H

### checks if D is square-free ### def square_free(D): F = factor(D) for X in F: if X[1] > 1: return false return true

### checks if a number is a cube of an integer ### def is_cube(x): if type(x) != type(43): return false y = ZZ(sgn(x)* round( abs(x)^(1/3) ) ) return x == y^3

### checks if a number is a fundamental discriminant, and is thus suitable for computation of the Hilbert class polynomial (at least that is the case treated in the literature that I have managed to find) ### def fundamental_discriminant(D): if D >= -4: ### not really the standard definition of a fundamental discriminant, but useful return false if D % 4 == 1 and square_free(D): return true if D % 4 == 0: D1 = ZZ(D/4) if D1 % 4 == 1 or D1 % 4 == 0: return false if not square_free(D1): return false return true return false

### tests an algorithm for computing the Hilbert class polynomial, comparing it against the one implemented in SAGE ### def test_hilbert_class_polynomial( hcp , silent = true, test_number = 10, maxD = -10, minD = -100): for test_iter in range(test_number): D = 0 while not fundamental_discriminant(D): D = randint(minD, maxD) if fundamental_discriminant(D): if not silent: print "D:", D H_comp = ZZ[X](hcp(D)) H_real = ZZ[X](hilbert_class_polynomial(D)(X)) H_diff = simplify(H_comp - H_real) pas = simplify( H_diff == ZZ[X](0) ) if not silent: print "Computed H_D:", H_comp print "Correct H_D:", H_real print "Difference :", H_diff print "Correct :", pas if not pas: raise ArithmeticError("The computed polynomial is wrong! Test failed!") print " " print "Test passed!"

### run the test of Hilbert class polynomial ### test_hilbert_class_polynomial(find_H, silent = true, test_number = 10, maxD = -10, minD = -100)

Test passed!

Test passed!

### finds an element of F(p) which is not a square ### def find_non_square(p): K = FiniteField(p) for c in K: if c^((p-1)/2) != K(1) and c != K(0): return c

### finds an elliptic curve over F(p) with the given j-invariant j0 ### def find_curve_given_j(j0, p): x,y = var('x,y') K = FiniteField(p) k = j0/(K(1728)-j0) E = EllipticCurve(K, [3*k, 2*k] ) j1 = E.j_invariant() if j1 != j0: raise ArithmeticError("Something wrong while constructing the curve given j0!") return E

### finds an elliptic curve over F(p) with the given j-invariant j0; the result is a twisted version of find_curve_given_j(j0,p) ### def find_twisted_curve_given_j(j0, p): x,y = var('x,y') K = FiniteField(p) k = j0/(K(1728)-j0) c = find_non_square(p) E = EllipticCurve(K, [3*k*c^2, 2*k*c^3] ) j1 = E.j_invariant() if j1 != j0: raise ArithmeticError("Something wrong while constructing the curve given j0!") return E

### takes the squares out of D, except for powers of two, of which it leaves at leas two, if present; returns [s,D/s^2] ### def reduce_squares(D): F = factor(D) s = 1 for i in range( len(F) ): if F[i][0] != 2: s *= F[i][0]^( ZZ( floor(F[i][1]/2) ) ) else: if F[i][1] >= 4 : s *= F[i][0]^( ZZ( floor((F[i][1]-2)/2) ) ) return [s, D/s^2]

### the main goal: find an elliptic curve (over some F(p)) with exactly N points ### def find_curve(N, silent = true, max_D = 10^4): vars_set = false p = None while not vars_set: p = find_prime(N, p) t = p+1-N D = -(4*p - t^2) s_and_D = reduce_squares(D) s = s_and_D[0] D = s_and_D[1] if fundamental_discriminant(D) and abs(D) <= max_D: vars_set = true if not silent: print "N:", N print "p:", p print "t:", t print "D:", D print "s:", s H = find_H(D) K = FiniteField(p) H = K[X](H) J_and_Deg = H.roots() for j_and_deg in J_and_Deg: j = j_and_deg[0] if j != K(0) and j != K(1728): E1 = find_curve_given_j(j,p) N1 = E1.cardinality() if not silent: print "Cardinality (non-twisted):",N1 if N1 == N: return E1 E2 = find_twisted_curve_given_j(j,p) N2 = E2.cardinality() if not silent: print "Cardinality (twisted):",N2 if N2 == N: return E2

### tests the implementation of the function find_curve ### def test_find_curve_once(fc, N, silent = true): if not silent: print "Looking for a curve with", N, "points" E = fc(N, silent = silent) if E == None: print "FAIL! No curve found!" raise ArithmeticError("FAIL!") else: if not silent: print "Found", E, "which has", E.cardinality(), "points" pas = E.cardinality() == N if pas and not silent: print "Answer correct!" if not pas: raise ArithmeticError("FAIL! Wrong cardinality of the curve!") def test_find_curve(fc, test_number = 10, N_max = 1000, N_min = 100, silent = true): for test_iter in range(test_number): N = randint(N_min, N_max) test_find_curve_once(fc, N, silent = silent) print "TEST PASSED! The program works, probably;)"

### run the tests ### test_find_curve(find_curve, test_number = 1, N_max = 100, N_min = 50, silent = false) test_find_curve(find_curve, test_number = 10, N_max = 2000, N_min = 1000, silent = false) test_find_curve(find_curve, test_number = 100, N_max = 10000, N_min = 1000, silent = true)

Looking for a curve with 71 points
N: 71
p: 59
t: -11
D: -115
s: 1
Cardinality (non-twisted): 71
Found Elliptic Curve defined by y^2 = x^3 + 35*x + 43 over Finite Field
of size 59 which has 71 points
Answer correct!
TEST PASSED! The program works, probably;)
Looking for a curve with 1821 points
N: 1821
p: 1907
t: 87
D: -59
s: 1
Cardinality (non-twisted): 1821
Found Elliptic Curve defined by y^2 = x^3 + 1833*x + 1222 over Finite
Field of size 1907 which has 1821 points
Answer correct!
Looking for a curve with 1708 points
N: 1708
p: 1777
t: 70
D: -552
s: 2
Cardinality (non-twisted): 1848
Cardinality (twisted): 1708
Found Elliptic Curve defined by y^2 = x^3 + 1676*x + 848 over Finite
Field of size 1777 which has 1708 points
Answer correct!
Looking for a curve with 1722 points
N: 1722
p: 1801
t: 80
D: -804
s: 1
Cardinality (non-twisted): 1882
Cardinality (twisted): 1722
Found Elliptic Curve defined by y^2 = x^3 + 327*x + 597 over Finite
Field of size 1801 which has 1722 points
Answer correct!
Looking for a curve with 1763 points
N: 1763
p: 1847
t: 85
D: -163
s: 1
Cardinality (non-twisted): 1763
Found Elliptic Curve defined by y^2 = x^3 + 1325*x + 1499 over Finite
Field of size 1847 which has 1763 points
Answer correct!
Looking for a curve with 1063 points
N: 1063
p: 1123
t: 61
D: -771
s: 1
Cardinality (non-twisted): 1063
Found Elliptic Curve defined by y^2 = x^3 + 929*x + 245 over Finite
Field of size 1123 which has 1063 points
Answer correct!
Looking for a curve with 1875 points
N: 1875
p: 1949
t: 75
D: -2171
s: 1
Cardinality (non-twisted): 1875
Found Elliptic Curve defined by y^2 = x^3 + 534*x + 356 over Finite
Field of size 1949 which has 1875 points
Answer correct!
Looking for a curve with 1964 points
N: 1964
p: 1889
t: -74
D: -520
s: 2
Cardinality (non-twisted): 1816
Cardinality (twisted): 1964
Found Elliptic Curve defined by y^2 = x^3 + 314*x + 628 over Finite
Field of size 1889 which has 1964 points
Answer correct!
Looking for a curve with 1553 points
N: 1553
p: 1627
t: 75
D: -883
s: 1
Cardinality (non-twisted): 1553
Found Elliptic Curve defined by y^2 = x^3 + 52*x + 577 over Finite Field
of size 1627 which has 1553 points
Answer correct!
Looking for a curve with 1317 points
N: 1317
p: 1381
t: 65
D: -1299
s: 1
Cardinality (non-twisted): 1317
Found Elliptic Curve defined by y^2 = x^3 + 702*x + 468 over Finite
Field of size 1381 which has 1317 points
Answer correct!
Looking for a curve with 1149 points
N: 1149
p: 1217
t: 69
D: -107
s: 1
Cardinality (non-twisted): 1287
Cardinality (twisted): 1149
Found Elliptic Curve defined by y^2 = x^3 + 75*x + 150 over Finite Field
of size 1217 which has 1149 points
Answer correct!
TEST PASSED! The program works, probably;)
TEST PASSED! The program works, probably;)

Looking for a curve with 71 points
N: 71
p: 59
t: -11
D: -115
s: 1
Cardinality (non-twisted): 71
Found Elliptic Curve defined by y^2 = x^3 + 35*x + 43 over Finite Field of size 59 which has 71 points
Answer correct!
TEST PASSED! The program works, probably;)
Looking for a curve with 1821 points
N: 1821
p: 1907
t: 87
D: -59
s: 1
Cardinality (non-twisted): 1821
Found Elliptic Curve defined by y^2 = x^3 + 1833*x + 1222 over Finite Field of size 1907 which has 1821 points
Answer correct!
Looking for a curve with 1708 points
N: 1708
p: 1777
t: 70
D: -552
s: 2
Cardinality (non-twisted): 1848
Cardinality (twisted): 1708
Found Elliptic Curve defined by y^2 = x^3 + 1676*x + 848 over Finite Field of size 1777 which has 1708 points
Answer correct!
Looking for a curve with 1722 points
N: 1722
p: 1801
t: 80
D: -804
s: 1
Cardinality (non-twisted): 1882
Cardinality (twisted): 1722
Found Elliptic Curve defined by y^2 = x^3 + 327*x + 597 over Finite Field of size 1801 which has 1722 points
Answer correct!
Looking for a curve with 1763 points
N: 1763
p: 1847
t: 85
D: -163
s: 1
Cardinality (non-twisted): 1763
Found Elliptic Curve defined by y^2 = x^3 + 1325*x + 1499 over Finite Field of size 1847 which has 1763 points
Answer correct!
Looking for a curve with 1063 points
N: 1063
p: 1123
t: 61
D: -771
s: 1
Cardinality (non-twisted): 1063
Found Elliptic Curve defined by y^2 = x^3 + 929*x + 245 over Finite Field of size 1123 which has 1063 points
Answer correct!
Looking for a curve with 1875 points
N: 1875
p: 1949
t: 75
D: -2171
s: 1
Cardinality (non-twisted): 1875
Found Elliptic Curve defined by y^2 = x^3 + 534*x + 356 over Finite Field of size 1949 which has 1875 points
Answer correct!
Looking for a curve with 1964 points
N: 1964
p: 1889
t: -74
D: -520
s: 2
Cardinality (non-twisted): 1816
Cardinality (twisted): 1964
Found Elliptic Curve defined by y^2 = x^3 + 314*x + 628 over Finite Field of size 1889 which has 1964 points
Answer correct!
Looking for a curve with 1553 points
N: 1553
p: 1627
t: 75
D: -883
s: 1
Cardinality (non-twisted): 1553
Found Elliptic Curve defined by y^2 = x^3 + 52*x + 577 over Finite Field of size 1627 which has 1553 points
Answer correct!
Looking for a curve with 1317 points
N: 1317
p: 1381
t: 65
D: -1299
s: 1
Cardinality (non-twisted): 1317
Found Elliptic Curve defined by y^2 = x^3 + 702*x + 468 over Finite Field of size 1381 which has 1317 points
Answer correct!
Looking for a curve with 1149 points
N: 1149
p: 1217
t: 69
D: -107
s: 1
Cardinality (non-twisted): 1287
Cardinality (twisted): 1149
Found Elliptic Curve defined by y^2 = x^3 + 75*x + 150 over Finite Field of size 1217 which has 1149 points
Answer correct!
TEST PASSED! The program works, probably;)
TEST PASSED! The program works, probably;)

#test_find_curve_once(find_curve, 4343, silent = false) test_find_curve_once(find_curve, 43^6, silent = false) #test_find_curve_once(find_curve, 43434343, silent = false) #test_find_curve_once(find_curve, 4343434343, silent = false) #test_find_curve_once(find_curve, 434343434343, silent = false) #test_find_curve_once(find_curve, 43434343434343, silent = false) #test_find_curve_once(find_curve, 43^7, silent = false) #test_find_curve_once(find_curve, 43^8, silent = false) #test_find_curve_once(find_curve, 43^9, silent = false) #test_find_curve_once(find_curve, 43^10, silent = false) #test_find_curve_once(find_curve, 43^11, silent = false) #test_find_curve_once(find_curve, 43^12, silent = false)

Looking for a curve with 6321363049 points
N: 6321363049
p: 6321521677
t: 158629
D: -7387
s: 129
Cardinality (non-twisted): 6321363049
Found Elliptic Curve defined by y^2 = x^3 + 2891732160*x + 1927821440
over Finite Field of size 6321521677 which has 6321363049 points
Answer correct!

Looking for a curve with 6321363049 points
N: 6321363049
p: 6321521677
t: 158629
D: -7387
s: 129
Cardinality (non-twisted): 6321363049
Found Elliptic Curve defined by y^2 = x^3 + 2891732160*x + 1927821440 over Finite Field of size 6321521677 which has 6321363049 points
Answer correct!

################## ### THE ANSWER ### ################## # # My favorite number is (obviously) 43. # This number is generally believed (at least among mathematicians and physicists at the Jagellonian University) to be the most significant number in the universe (or at least to occur *much* more often than statistics and common sense would suggest). As a means of checking that the number 43 was there before I started writing the above algorithms, you may check that I am actually a member of a facebook 43-related group: http://www.facebook.com/group.php?gid=49363852536 (you might also want to see http://www.facebook.com/group.php?gid=150968688257432&v=info). # The number 43 is sadly not a very impressive one for algorithmic purposes. I have thus decided to use the number 43^6. The presence of 43 is natural, and 6 is a perfect number. Once, when I was in high school a teacher was discussing grades, and he pointed out that 2 was, in his opinion, perfect (it is the lowest passing grade in Polish schools, and as a matter of fact, there were quite a few of them). Feeling righteous indignation at such mistreatment of mathematics, I informed him that 2 is, in fact, not perfect, although 6 is, and presented a short justification of the fact on the blackboard. From then on, I feel connected to the number 6. # Now that you know my story, I hope you'll find my number acceptable. # The test above produces quite readable output, I hope. Note that the testing function does in fact use SAGE's .cardinality() function (in fact, it is called twice; once to test what output to produce, and second time so that it is explicitly visible that it is actually called). I did not find any specific information regarding function names and return values (to get the curve on output, use find_curve(N)) # As for the code, I believe that what happens is quite self-explanatory. Why it happens was more or less discussed during the lecture, and it makes little sense for me to write this here once again. As a reference source I used a pdf which I found on the web: # Bjarki Holm, 'Constructing Elliptic Curves with a Given Number of Points', University of Cambridge, Hughes Hall # and which is highly googlable. # Note: the algorithm sometimes fails for *small* values of N. I don't consider it a bug because in those cases one could just apply brute force and get the result quickly anyway. The algorithm is meant for sufficiently large N, and for those values I believe it always works. # Note: I did my best to avoid calling hilbert_class_polynomial, since I believe it does indeed leave little left for one to implement. It is however used if the program is unable to compute the appropriate polynomial by itself. I hope it is not regarded as inappropriate. # Note: for the sake of completeness, the curve is: Elliptic Curve defined by y^2 = x^3 + 2891732160*x + 1927821440 over Finite Field of size 6321521677 which has 6321363049 points

final

157 days ago by jakub.konieczny