logarithm-finding.md

Examples: Finding discrete logarithms in $\mathbb Z_p^*$

Prerequisites

Launch Sage and load the logarithm-finding.sage script by executing:

$ sage
(..)
sage: load("logarithm-finding.sage")

Simulating the quantum algorithm

To simulate solving the discrete logarithm in $\mathbb Z_p^*$ for $p$ an $n$-bit prime, first setup such a prime on special form, together with a generator $g$, by executing:

sage: n = 2048
sage: [g, p] = sample_domain_parameters_safe_prime(n, verbose = True)
Sampling domain parameters...

 Sampled p = 19485592699019952433467031008633465217039386817146006130092333102188307808996571817597257944714320769319526355092088254264510942291551255115434541916356088697923914147220097147753883879231784246419075882437160984897225685578436285997734644604108679255476391939857110224050119899645870266200149210991939724488579750666276965595459615282072128643588045912023571743928965742704885138796044385532150903083656589802389602548723278599695606772643193421165406935291585953227930440068957488098834736219879945004500616752781763449340772350488569363738173332022154822794642795180218954706449916297210487369794314164258030157007
 Sampled g = 2

 Time required to sample: 730 ms 158 µs

This yields $p$ and $g$ for a simulated safe-prime group $\langle g \rangle \subset \mathbb Z_p^*$.

To instead generate $p$ and $g$ for a simulated Schnorr group, with $g$ of order approximately $2^{224}$ and $n$ as above, execute:

sage: [g, p] = sample_domain_parameters_schnorr(n, 224, verbose = True)
Sampling domain parameters...
 Sampled p = 21946882222603507201358549656602239350758495620248627416043148425115876139032349307738134144070499678290111479834834434686394407765907750937719305062047608115858969060849871479077931163486349858472348800947974909491866521899417684524446395193115340942937989094412814267045964564960436747907325769739560424103037390952067456867339304752295741480973542967341657395654063491125512777099142220840755489255975816393244308166699184895063551341731939176154204996791722526480178508969034786373690291226888607534177452900757971502601114256576027126254932255777384842332462198754818602267968704862026952954250433785375526223367
 Sampled g = 18577044198305986797836304185942455821714463850193324640157932486337840718329234404422420329601848929009383011407647269783914653557656685262887966134160139279491363843495191151384596565295358411753152519974916085060220152298969887063047151126203508069903172441679808715933213481914653650736947731670018185735904802076884569854782749497900122791354352602062339814297033625198408006535133707263677027841563152586773221413613376748770032426756500814653646174893628307627099651585191786649940412884302601402313246906273602292763284915044287273716599915531725253430637072345778199475165740909481358951619682488870829379127

 Time required to sample: 4 sec 766 ms 22 µs

Next, to generate a random problem instance $x = g^e$, execute:

sage: [x, e] = sample_x(g, p)

Finally, generate a basis for the $d$-dimensional lattice for this problem instance, where $d = \lceil \sqrt{n} \rceil$, by executing:

sage: d = ceil(sqrt(n))
sage: B = generate_basis_for_logarithm_finding(p, u = [x, g], d = d, verbose = True)
Generating a basis for the lattice L...
 Sampling vectors from L...
  Sampling vectors 1 to 8 of 54 using 8 threads...
  Sampling vectors 9 to 16 of 54 using 8 threads...
  Sampling vectors 17 to 24 of 54 using 8 threads...
  Sampling vectors 25 to 32 of 54 using 8 threads...
  Sampling vectors 33 to 40 of 54 using 8 threads...
  Sampling vectors 41 to 48 of 54 using 8 threads...
  Sampling vectors 49 to 54 of 54 using 8 threads...

 Reducing the basis for L, this may take a moment...

 Time required to generate a basis for L: 1 min 26 sec 375 ms 797 µs

This basis can then be used to setup the simulator by executing:

sage: simulator = Simulator(B, verbose = True)
Setting up the simulator...
 Computing the basis for the dual L^* of L...
 Computing the Gram–Schmidt orthogonalization of the basis...

 Time required to setup the simulator: 7 sec 674 ms 364 µs

Finally, simulate running the quantum algorithm $d + 4$ times with $C = 2$ by executing:

sage: C = 2
sage: R = get_regev_R(C, n)
sage: samples = simulator.sample_vectors(R, verbose = True)
Sampling 50 good vectors and 0 bad vectors...
 Sampling vectors 1 to 8 of 50 using 8 threads...
 Sampling vectors 9 to 16 of 50 using 8 threads...
 Sampling vectors 17 to 24 of 50 using 8 threads...
 Sampling vectors 25 to 32 of 50 using 8 threads...
 Sampling vectors 33 to 40 of 50 using 8 threads...
 Sampling vectors 41 to 48 of 50 using 8 threads...
 Sampling vectors 49 to 50 of 50 using 2 threads...

 Time required to sample: 3 sec 244 ms 363 µs

Executing the classical post-processing

To solve the samples for the discrete logarithm $e$, execute:

sage: e_found = solve_samples_for_logarithm(samples, g, x, p, R, verbose = True)
Post-processing the sampled vectors to find the logarithm...
 Building the post-processing matrix...
 Running LLL on the post-processing matrix...
  Found 46 / 46 linearly independent vectors...

 Found e = 1802525546752374799735962366655386682495532156475534240382179787923736
 Found r = 37487212230433464197884555702448875843509318596088464655735067775451923

 Time required to post-process: 12 sec 268 ms 62 µs

Convenience test function

There are also convenience test functions that perform the above procedure for either Schnorr groups or safe-prime groups.

To try it out for a safe-prime group with $p$ of length $512$ bits, execute:

sage: result = test_logarithm_finding_in_safe_prime_group(512, verbose = True)
** Setting up the problem instance...

Sampling domain parameters...

 Sampled p = 8781592102924542433277381339894428265566457217060819810035757170050531247754405317394331924839687599178527590506556571515699709189921516329302699240360239
 Sampled g = 2

 Time required to sample: 17 ms 22 µs

 Sampled e = 23485220857917533380310871465019166491025287668501356756124727383508765457633028210177208758716194870174946348137649596392457177731484985615835267497215
 Computed x = g^e mod p = 3376126482259577664406372998993937019790660839862643959353326938764366864852882123384662324907308486087009518960841339096744801145834964981211548153176285

** Setting up the simulator...

Generating a basis for the lattice L...
 Sampling vectors from L...
  Sampling vectors 1 to 8 of 31 using 8 threads...
  Sampling vectors 9 to 16 of 31 using 8 threads...
  Sampling vectors 17 to 24 of 31 using 8 threads...
  Sampling vectors 25 to 31 of 31 using 8 threads...

 Reducing the basis for L, this may take a moment...

 Time required to generate a basis for L: 1 sec 219 ms 893 µs

Setting up the simulator...
 Computing the basis for the dual L^* of L...
 Computing the Gram–Schmidt orthogonalization of the basis...

 Time required to setup the simulator: 259 ms 687 µs

** Sampling vectors...

Sampling 27 good vectors and 0 bad vectors...
 Sampling vectors 1 to 8 of 27 using 8 threads...
 Sampling vectors 9 to 16 of 27 using 8 threads...
 Sampling vectors 17 to 24 of 27 using 8 threads...
 Sampling vectors 25 to 27 of 27 using 3 threads...

 Time required to sample: 317 ms 223 µs

** Solving for the logarithm...

Post-processing the sampled vectors to find the logarithm...
 Building the post-processing matrix...
 Running LLL on the post-processing matrix...
  Found 23 / 23 linearly independent vectors...

 Found e = 23485220857917533380310871465019166491025287668501356756124727383508765457633028210177208758716194870174946348137649596392457177731484985615835267497215
 Found r = 4390796051462271216638690669947214132783228608530409905017878585025265623877202658697165962419843799589263795253278285757849854594960758164651349620180119

 Time required to post-process: 414 ms 45 µs
sage: print(f"Found the expected discrete logarithm: {result}")
Found the expected discrete logarithm: True

To try it out for a Schnorr group of order approximately $2^{112}$ with $p$ of length $512$ bits, instead execute:

sage: result = test_logarithm_finding_in_schnorr_group(512, 112, verbose = True)
** Setting up the problem instance...

Sampling domain parameters...
 Sampled p = 6805914063141485515864171483611657494966515840821051124450630932560350634059537805427341887581703710099331176085625742831181936616313532501173063244415063
 Sampled g = 2346364588987831265430934752683855558348055853181484919258081219902477339690592543621230871707412113090769086266169773660221829443764026167265600133685146

 Time required to sample: 22 ms 290 µs

 Sampled e = 25421664306484183296140339447946259
 Computed x = g^e mod p = 5647395744355420553517663216390016707327533291209587751821989399294901364039845520978540405927727645551265092905215257112857780031630661767596015908942576

** Setting up the simulator...

Generating a basis for the lattice L...
 Sampling vectors from L...
  Sampling vectors 1 to 8 of 31 using 8 threads...
  Sampling vectors 9 to 16 of 31 using 8 threads...
  Sampling vectors 17 to 24 of 31 using 8 threads...
  Sampling vectors 25 to 31 of 31 using 8 threads...

 Reducing the basis for L, this may take a moment...

 Time required to generate a basis for L: 1 sec 349 ms 693 µs

Setting up the simulator...
 Computing the basis for the dual L^* of L...
 Computing the Gram–Schmidt orthogonalization of the basis...

 Time required to setup the simulator: 206 ms 748 µs

** Sampling vectors...

Sampling 27 good vectors and 0 bad vectors...
 Sampling vectors 1 to 8 of 27 using 8 threads...
 Sampling vectors 9 to 16 of 27 using 8 threads...
 Sampling vectors 17 to 24 of 27 using 8 threads...
 Sampling vectors 25 to 27 of 27 using 3 threads...

 Time required to sample: 214 ms 180 µs

** Solving for the logarithm...

Post-processing the sampled vectors to find the logarithm...
 Building the post-processing matrix...
 Running LLL on the post-processing matrix...
  Found 23 / 23 linearly independent vectors...

 Found e = 25421664306484183296140339447946259
 Found r = 212924088970898152852623453524541821

 Time required to post-process: 323 ms 232 µs
sage: print(f"Found the expected discrete logarithm: {result}")
Found the expected discrete logarithm: True

Note that there are many optional parameters that can be passed to the above convenience functions, and to the functions they in turn call, allowing the simulation, sampling and post-processing to be tweaked in various ways. For further details, please see the source code documentation for the aforementioned functions.