Skip to content

README.md

Latest commit

 

History

History
70 lines (57 loc) · 5.8 KB

README.md

File metadata and controls

70 lines (57 loc) · 5.8 KB

Isogeny

DOI

Code to efficiently compute the directed supersingular isogeny graph G(p, L), written in PARI/GP. This allows for L = integer or vector of integers, currently restricted to at most 17. For larger l, it requires downloading and processing the relevant modular polynomials (see modpol_processraw for more details).

There is currently code built-in to SageMath to do this, however this project allows for non-prime l as well as L-isogeny graphs, and it is significantly faster than the Sage implementation (approximate speedups were computed with up-to-date PARI/GP and SageMath installations in Fall 2023):

  • l = 2, about 67 times as fast
  • l = 3, about 107 times as fast
  • l = 5, about 211 times as fast
  • l = 7, about 217 times as fast

This project can be used from PARI/GP as well as Sage. See below for general installation instructions, and here for a more detailed Users Guide, including details on using the package directly from Sage.

Bibtex

If you use this code in a project, please let me know! Here is a Bibtex entry that points to the latest version. You may wish to update the version number to the one you used.

@software{IsogenyCode,
	AUTHOR = {Rickards, James},
	DOI = {10.5281/zenodo.20402071},
	LICENSE = {GPL-3.0},
	TITLE = {{Isogeny}},
	URL = {https://github.com/JamesRickards-Canada/Isogeny},
	YEAR = {2026},
	VERSION = {1.0.0},
}

Installation Instructions

Downloading the code

Call git clone https://github.com/JamesRickards-Canada/Isogeny.git. If you are on Windows, be sure to git clone from WSL (see below), as Windows line endings (carriage returns) may be added to files, causing issues.

Prerequisites

  • PARI/GP, but not the downloaded ready-to-go binary. The PARI/GP website has binaries for Windows and Mac avaliable, but these will not work with the package. See below for OS specific instructions.
  • You should have a guess as to the location of the pari.cfg file for the version of PARI/GP you are running. Suggestions on how to do this can be found below.
  • This package has been tested on versions:

2.15.3 - 2.15.5,   2.17.0 - 2.17.3,   2.18.1

  • If you try to use it on a different version, be aware that it may not work.
  • If you want to use this package through Sage, you need to find the copy of PARI/GP installed with Sage!

Operating systems

  • Linux - No further requirements
  • Windows - You need to use Windows Subsytem for Linux. See the guide I wrote for additional instructions.
  • Mac - You need to have Homebrew installed. This is also an easy way to install PARI/GP: brew install pari

Configuring and building the package

  • From inside the project folder, call ./configure to initialize the project. This helps you search for pari.cfg, and stores the location to a file. You should supply it with a folder to search in!
  • The script displays the corresponding versions of the found files, so if you have multiple versions, you can choose the correct one. This can be useful if you keep multiple copies of PARI/GP around.
  • If the location of the installation of PARI/GP does not change, you do not need to reconfigure. If when you update PARI/GP there is a new location (e.g. if the version number is in the file path of pari.cfg), you should call ./configure again.
  • Call make to build the project, and make clean to remove all .o object files. If you update to a new version of PARI/GP, you must make clean and then make again.

Running the package

  • Once this is done, a call to gp isogeny starts gp with the package installed!
  • Further updates to the package (that you download with git pull) just require calling make again.
  • Call ?isogeny to access further help.

Where is pari.cfg?

  • The configuration file will search for this, but it is preferrable to not search your entire hard drive (as this can be very slow). So, you should at least supply a guess as to the location of pari.cfg. Often only the top-level folder (e.g. /usr or /opt) suffices.
  • On Linux or WSL, if you build PARI/GP from source, it should be located in /usr/local/lib/pari/pari.cfg, or at least somewhere in the /usr folder.
  • On a Mac, if you install PARI/GP with Homebrew, it may be found in a folder like /opt/homebrew/Cellar/pari/VERSION/lib/pari. Searching /opt/homebrew should be fine.
  • If you are obtaining it through Sage, it might be found where the library files of Sage are
  • Assuming you open PARI/GP with the command gp, try type -a gp, which will display where this command lives. The corresponding file(s) are likely symbolic links, and you can call readlink -f LOCATION on each of them to see where it lives. This can provide a clue as to the place to search for pari.cfg.
  • Another clue comes from gp itself. Open gp, and type default(). Look for the entries datadir and help. It is often the case that datadir is in X/share/pari, help is in X/bin/gphelp, and pari.cfg is in X/lib/pari/pari.cfg.

Troubleshooting

  • If you are encoutering unexpected errors or warnings when building, ensure you found the correct pari.cfg file. You need to configure the project with the same installation of PARI/GP that you will run it with.
  • If you change versions of PARI/GP, the package needs to be rebuilt: make clean to reset the object files, reconfigure with ./configure, and then run make again.
  • When in doubt, rebuild the project as above to troubleshoot.
  • If you have any further issues with installation or using the code, please let me know!