{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def HEC(f):\n", " try:\n", " res = HyperellipticCurve(f)\n", " except ValueError:\n", " return 'singular'\n", " return res\n", "\n", "def HEC_random(genus, q, imag=True):\n", " R. = GF(q)['x']\n", " d = 0\n", " while d == 0:\n", " pol = 0\n", " if imag:\n", " pol = R.random_element(degree=2*genus+1).monic()\n", " else:\n", " pol = R.random_element(degree=2*genus+2).monic()\n", " d = pol.discriminant()\n", " return HyperellipticCurve(pol)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Build the list of possible pairs [a1,a2,prob] given the Frobenius order r on A[l]\n", "# and precomputed probability prob of the order r\n", "#@parallel(\"multiprocessing\", ncpus=4)\n", "@parallel(ncpus=6)\n", "def enum_zetas(r, i, zeta, l, q, prob):\n", " L = []\n", " Fl = GF(l)\n", " for j in range(i, ceil(r/2)+1):\n", " if (lcm(r/gcd(i,r), r/gcd(j,r)) != r) and (lcm(r/gcd(i,r), r/gcd(j,r)) != r/2):\n", " continue\n", " zeta_1 = zeta^i\n", " zeta_2 = zeta^j\n", " #\n", " eta_1 = zeta_1 + 1/zeta_1 + 2\n", " eta_2 = zeta_2 + 1/zeta_2 + 2\n", " #\n", " eta_12 = eta_1 * eta_2\n", " if (eta_12^l != eta_12) or (not eta_12.is_square()):\n", " continue\n", " eta_12_r = eta_12.sqrt()\n", " \n", " a1_sq_list = [(eta_1 + eta_2 + 2*eta_12_r)*q, (eta_1 + eta_2 - 2*eta_12_r)*q]\n", " a2_2q_sq = eta_12*q^2\n", " for a1_sq in a1_sq_list:\n", " if is_square(a1_sq) and a1_sq^l == a1_sq:\n", " if not ([a1_sq, a2_2q_sq, prob] in L):\n", " L.append([a1_sq, a2_2q_sq, prob])\n", " return L\n", "\n", "def build_list_by_order(l, r, q, prob):\n", " k = Mod(l,r).multiplicative_order()\n", " print \"-> L for r={}, l={}: primitive r-th root belongs to Fl^{}\".format(r,l,k)\n", " Fl = GF(l)\n", " Flk = Fl.extension(k)\n", " zeta = Flk.zeta(r)\n", " R. = Flk['T']\n", " L = []\n", " v = list(enum_zetas( [(r, i, zeta, l, q, prob) for i in range(ceil(r/2)+1)] ))\n", " for arg,res in v:\n", " for t in res:\n", " if not t in L:\n", " L.append(t)\n", " return L" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def build_list(l, q, probs):\n", " check_list = {}\n", " L = []\n", " for r,prob in probs:\n", " if denominator(r) == 1:\n", " S = build_list_by_order(l, r, q, prob)\n", " for s,t,prob in S:\n", " found = False\n", " for i in range(len(L)):\n", " sl,tl,probl = L[i]\n", " if sl == s and tl == t:\n", " L[i] = [s,t, prob/len(S)+probl]\n", " found = True\n", " break\n", " if not found:\n", " L.append([s,t,prob/len(S)])\n", " check_list[str([s,t])] = True\n", " print \"-> L size without padding:\", len(L)\n", " Fl = GF(l)\n", " for s in Fl:\n", " for t in Fl:\n", " if (not is_square(s)) or (not is_square(t)):\n", " continue\n", " if not check_list.has_key(str([s,t])):\n", " L.append([s,t,0])\n", " return sorted(L, key=lambda tup: tup[2], reverse=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def count_tries_L(frob, l, q, lst=None):\n", " count = 1\n", " Fl = GF(l)\n", " Rl. = Fl['T']\n", " frob_l = frob.change_ring(Fl).change_variable_name(\"T\")\n", " a1l = frob_l.coefficients(sparse=False)[3]\n", " a2l = frob_l.coefficients(sparse=False)[2]\n", " sl = a1l^2\n", " tl = (a2l-2*q)^2\n", " if lst == None:\n", " L = build_list(l,q)\n", " else:\n", " L = lst\n", " for s,t,prob in L:\n", " if (s==sl) and (t==tl):\n", " return count\n", " count = count + 1\n", " print \"count_tries_L(): not found\"\n", " return None # not in the list\n", "\n", "def count_tries_bruteforce(frob, l, q, limit=None):\n", " count = 1\n", " Fl = GF(l)\n", " Rl. = Fl['T']\n", " frob_l = frob.change_ring(Fl).change_variable_name(\"T\")\n", " a1l = frob_l.coefficients(sparse=False)[3]\n", " a2l = frob_l.coefficients(sparse=False)[2]\n", " if frob_l != T^4 + a1l*T^3 + a2l*T^2 + a1l*q*T + q^2:\n", " print \"Error in count_tries_bruteforce()\"\n", " sl = a1l^2\n", " tl = (a2l-2*q)^2\n", " for s in Fl:\n", " for t in Fl:\n", " if limit != None and count > limit:\n", " print \"Warning: count_tries_bruteforce() limit reached\"\n", " return None\n", " if (not is_square(s)) or (not is_square(t)):\n", " continue\n", " if (s==sl) and (t==tl):\n", " return count\n", " count = count + 1\n", " print \"Error: count_tries_bruteforce(), not found\"\n", " return None # error" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def sample_curves(N, g, q, imag=True):\n", " res = []\n", " for i in range(N):\n", " C = HEC_random(g,q, imag)\n", " res.append(C)\n", " return res" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "g = 2\n", "H = (9*g+3)\n", "l_min = 5\n", "l_max = 300\n", "curves_N = 10000\n", "C_count = 0\n", "\n", "primes_N = 1000000\n", "p_bound = 2^18\n", "p_lbound = 2^16\n", "\n", "i = 1\n", "stats = []\n", "\n", "while i < primes_N:\n", " p = random_prime(p_bound, lbound=p_lbound)\n", " l_end = min(l_max,int(H*log(p)/log(2))+1)\n", " l_count = 0\n", " for l in prime_divisors(p-1):\n", " if not l in range(l_min, l_max):\n", " print [l,\"excluded\"]\n", " continue\n", " tries_for_p_L = 0\n", " tries_for_p_brute = 0\n", " print \"p = {}, l = {}\".format(p, l)\n", " print \"Building list ...\"\n", " probs = [[(l+1)/2, 0.04],[(l-1)/2, 0.04]]\n", " L = build_list(l,p, probs=probs)\n", " print \"-> done:\", len(L)\n", " print \"Sampling curves ...\"\n", " curves = sample_curves(curves_N, g, p)\n", " print \"-> done:\", len(curves)\n", " C_count = C_count + len(curves)\n", " for i in range(len(curves)):\n", " C = curves[i]\n", " frob = C.frobenius_polynomial()\n", " C1 = count_tries_L(frob, l, p, lst=L)\n", " brute_limit = len(L)\n", " C2 = count_tries_bruteforce(frob, l, p, limit=brute_limit)\n", " #print \"-> Curve:{}, SearchInList: {}, Bruteforce: {}\".format(i, C1, C2)\n", " if C1 != None and C2 != None:\n", " tries_for_p_L = tries_for_p_L + C1\n", " tries_for_p_brute = tries_for_p_brute + C2\n", " if (i+1) % 1000 == 0:\n", " print \"Stats for {} curves: SearchInList: {}, Bruteforce: {}, {}\".format(i+1, tries_for_p_L, tries_for_p_brute, float(tries_for_p_L/tries_for_p_brute))\n", " l_ratio = float(tries_for_p_L/tries_for_p_brute)\n", " stats += [l_ratio]\n", " print \"Total for (p,l)=({},{}) (excluding None): SearchInList: {}, Bruteforce: {}, {}\".format(p, l, tries_for_p_L, tries_for_p_brute, l_ratio)\n", " print \"-------\\n\"\n", " l_count += 1\n", " if l_count > 0:\n", " print \"Stats:\", stats\n", " i = i + 1" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.9", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.15" } }, "nbformat": 4, "nbformat_minor": 2 }