Re: Pari/GP "halfgcd()" implementation

[Vincent Delecroix <vincent.delecroix@u-bordeaux.fr>]

If you want to use PARI/GP from Python you might want to have
a look at https://pypi.org/project/cypari2/

>>> import cypari2
>>> pari = cypari2.Pari()
>>> pari.halfgcd(123612348, 1342457)
[[38, -3499; -101, 9300], [12181, 2952]~]

Best
Vincent

Le 08/06/2023 à 22:56, hermann@stamm-wilbrandt.de a écrit :
> I really like Pari/GP "halfgcd()" function:
> https://pari.math.u-bordeaux.fr/pub/pari/manuals/2.15.1/users.pdf#page=204
>
> It allows very fast computation even on 388342-digit prime:
> Allows to determine  sqrt(-1) (mod p)  given sum of squares  p = x^2 + 
> y^2  (in 123ms on i7-11850H):
> https://forums.raspberrypi.com/viewtopic.php?p=2112166#p2112166
>
> I wanted to see whether it is possible to make "halfgcd()" available for 
> Python.
> Just did analyze "halfgcdii()" implementation in master branch 
> "pari/Olinux-aarch64/mpker.c".
> The huge C callgraph made me step away from that plan, I will simply use 
> Pari/GP instead.
> Details:
> https://forums.raspberrypi.com/viewtopic.php?p=2112412#p2112412
>
>
> This is test on potential mailing list URL restrictions.
> Below is the 24715 byte long GraphvizFiddle share link that display the 
> callgraph in GraphvizFiddle tool in browser.
> In case mailing list truncates it, the working link is in the posting 
> with details.
> (If you edit Graphviz .dot file in GraphvizFiddle, and then press 
> "Share" button, you get shareable URL)
>
> https://stamm-wilbrandt.de/GraphvizFiddle/2.1.2/index.html?1686255764085#strict%20digraph%20callgraph%20%7B%0A%22halfgcdii%22%20%5Bcolor%3Dblue%2C%20style%3Dfilled%5D%3B%0A%22halfgcdii%22%20-%3E%20%22abscmpii%22%20-%3E%20%22cmpiispec%22%20-%3E%20%22__gmpn_cmp%22%3B%0A%22__gmpn_cmp%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22cmpii%22%20-%3E%20%22cmpiispec%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22magic_threshold%22%20-%3E%20%22uexpi%22%20-%3E%20%22expi%22%20-%3E%20%22bit_accuracy%22%20-%3E%20%22prec2nbits%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22magic_threshold%22%20-%3E%20%22uexpi%22%20-%3E%20%22isint2n%22%20-%3E%20%22expu%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22cmpii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase
> %22%20-%3E%20%22lgcdii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22icopy_sign%22%20-%3E%20%22icopy%22%20-%3E%20%22new_chunk%22%20-%3E%20%22new_chunk_resize%22%3B%0A%22new_chunk_resize%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22icopy_sign%22%20-%3E%20%22icopy%22%20-%3E%20%22new_chunk%22%20-%3E%20%22set_avma%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22icopy_sign%22%20-%3E%20%22icopy%22%20-%3E%20%22evallg%22%20-%3E%20%22pari_err_OVERFLOW%22%20-%3E%20%22pari_err%22%3B%0A%22pari_err%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%
> 20-%3E%20%22addiispec%22%20-%3E%20%22adduispec%22%20-%3E%20%22adduu%22%20-%3E%20%22uutoi%22%20-%3E%20%22utoi%22%20-%3E%20%22utoipos%22%20-%3E%20%22cgetipos%22%20-%3E%20%22cgeti%22%20-%3E%20%22new_chunk%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22addiispec%22%20-%3E%20%22adduispec%22%20-%3E%20%22adduu%22%20-%3E%20%22uutoi%22%20-%3E%20%22utoi%22%20-%3E%20%22utoipos%22%20-%3E%20%22cgetipos%22%20-%3E%20%22cgeti%22%20-%3E%20%22evallg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22addiispec%22%20-%3E%20%22adduispec%22%20-%3E%20%22adduu%22%20-%3E%20%22uutoi%22%20-%3E%20%22cgetipos%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22addiispec%22%20-%3E%20%22adduispec%22%20-%3E%20%2
> 2cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22addiispec%22%20-%3E%20%22adduispec%22%20-%3E%20%22__gmpn_add_1%22%3B%0A%22__gmpn_add_1%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22addiispec%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22addiispec%22%20-%3E%20%22__gmpn_add%22%3B%0A%22__gmpn_add%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22cmpiispec%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E
> %20%22subiispec%22%20-%3E%20%22subiuspec%22%20-%3E%20%22utoi%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22subiispec%22%20-%3E%20%22subiuspec%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22subiispec%22%20-%3E%20%22subiuspec%22%20-%3E%20%22__gmpn_sub_1%22%3B%0A%22__gmpn_sub_1%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22subiispec%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22subii%22%20-%3E%20%22addii_sign%22%20-%3E%20%22subiispec%22%20-%3E%20%22__gmpn_sub%22%3B%0A%22__gmpn_sub%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20
> -%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22addii%22%20-%3E%20%22addii_sign%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mului%22%20-%3E%20%22muluispec%22%20-%3E%20%22muluu%22%20-%3E%20%22uutoi%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mului%22%20-%3E%20%22muluispec%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mului%22%20-%3E%20%22muluispec%22%20-%3E%20%22__gmpn_mul_1%22%3B%0A%22__gmpn_mul_1%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22muliu%22%20-%3E%20%22mului%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22togglesign%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22ex
> pi%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22pari_err_INV%22%20-%3E%20%22pari_err%22%3B%0A%22pari_err%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22__gmpn_cmp%22%3B%0A%22__gmpn_cmp%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22stoi%22%20-%3E%20%22utoipos%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22stoi%22%20-%3E%20%22utoineg%22%20-%3E%20%22cgetineg%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22icopy%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii
> %22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22__gmpn_divrem_1%22%3B%0A%22__gmpn_divrem_1%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22gc_const%22%20-%3E%20%22set_avma%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22set_avma%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22dvmdii%22%20-%3E%20%22__gmpn_tdiv_qr%22%3B%0A%22__gmpn_tdiv_qr%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mulii%22%20-%3E%20%22muliispec%22%20-%3E%20%22muluispec%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mulii%22%20-%3E%20%22mul
> iispec%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mulii%22%20-%3E%20%22muliispec%22%20-%3E%20%22__gmpn_mul%22%3B%0A%22__gmpn_mul%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22pari_warn%22%3B%0A%22pari_warn%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22copy_bin%22%3B%0A%22copy_bin%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22set_avma%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22bin_copy%22%20-%3E%20%22pari_free%22%20-%3E%20%22mt_sigint_block%22%3B%0A%22mt_sigint_block%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-
> %3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22bin_copy%22%20-%3E%20%22pari_free%22%20-%3E%20%22free%22%3B%0A%22free%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22bin_copy%22%20-%3E%20%22pari_free%22%20-%3E%20%22mt_sigint_unblock%22%3B%0A%22mt_sigint_unblock%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22bin_copy%22%20-%3E%20%22pari_free%22%20-%3E%20%22raise%22%3B%0A%22raise%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22bin_copy%22%20-%3E%20%22new_chunk%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22bin_copy%22%20-%3E%
> 20%22GENbinbase%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22bin_copy%22%20-%3E%20%22memcpy%22%3B%0A%22memcpy%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22pari_malloc%22%20-%3E%20%22mt_sigint_block%22%3B%0A%22mt_sigint_block%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22pari_malloc%22%20-%3E%20%22malloc%22%3B%0A%22malloc%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22pari_malloc%22%20-%3E%20%22mt_sigint_unblock%22%3B%0A%22mt_sigint_unblock%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepil
> eall%22%20-%3E%20%22pari_malloc%22%20-%3E%20%22raise%22%3B%0A%22raise%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22pari_malloc%22%20-%3E%20%22pari_err%22%3B%0A%22pari_err%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepileall%22%20-%3E%20%22pari_free%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mkmat22%22%20-%3E%20%22cgetg%22%20-%3E%20%22new_chunk%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mkmat22%22%20-%3E%20%22cgetg%22%20-%3E%20%22evallg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22mkmat22%22%20-%3E%20%22mkcol2%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%2
> 2HGCD_basecase%22%20-%3E%20%22mkvec3%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepilecopy%22%20-%3E%20%22is_recursive_t%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepilecopy%22%20-%3E%20%22copy_bin%22%3B%0A%22copy_bin%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepilecopy%22%20-%3E%20%22set_avma%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepilecopy%22%20-%3E%20%22bin_copy%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepilecopy%22%20-%3E%20%22new_chunk%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepilecopy%22%20-%3E%20%22leafcopy_avma%22%3B%0A%22halfgcdii%22%20-
> %3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_basecase%22%20-%3E%20%22gerepilecopy%22%20-%3E%20%22leafcopy%22%20-%3E%20%22new_chunk%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22magic_threshold%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22cmpii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22pari_err_BUG%22%20-%3E%20%22pari_err%22%3B%0A%22pari_err%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22expi%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22matid2%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22matid2%22%20-%3E%20%22mkcol2%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%
> 22HGCD_split%22%20-%3E%20%22mkvec3%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22gerepilecopy%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22icopyspec%22%20-%3E%20%22new_chunk%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22icopyspec%22%20-%3E%20%22evallg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22dvmdsBIL%22%20-%3E%20%22remsBIL%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22dvmdsBIL%22%20-%3E%20%22divsBIL%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22
> %20-%3E%20%22shiftispec%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22xmpn_copy%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22__gmpn_lshift%22%3B%0A%22__gmpn_lshift%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22__gmpn_rshift%22%3B%0A%22__gmpn_rshift%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22shifti%22%20-%3E%20%22shiftispec%22%20-%3E%20%22gc_const%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22addiu%22%20-%3E%20%22addui%22%20-%3E%20%22addui_sign%22%20-%3E%20%22icopy_sign%22%3B%0A%22halfgcdii%22%
> 20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22addiu%22%20-%3E%20%22addui%22%20-%3E%20%22addui_sign%22%20-%3E%20%22utoipos%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22addiu%22%20-%3E%20%22addui%22%20-%3E%20%22addui_sign%22%20-%3E%20%22adduispec%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22addiu%22%20-%3E%20%22addui%22%20-%3E%20%22addui_sign%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22addiu%22%20-%3E%20%22addui%22%20-%3E%20%22addui_sign%22%20-%3E%20%22subiuspec%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22cmpiu%22%20-%3E%20%22cmpui%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP0%22%20-%3E%20%22dvmdii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%
> 22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP0%22%20-%3E%20%22mulq%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP0%22%20-%3E%20%22mulq%22%20-%3E%20%22mulii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP0%22%20-%3E%20%22mulq%22%20-%3E%20%22addii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP0%22%20-%3E%20%22mulq%22%20-%3E%20%22mkcol2%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP0%22%20-%3E%20%22expi%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP0%22%20-%3E%20%22pari_err_BUG%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22HGCD%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HG
> CD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22remi2n%22%20-%3E%20%22dvmdsBIL%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22remi2n%22%20-%3E%20%22icopy%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22remi2n%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22signdet%22%20-%3E%20%22Mod4%22%20-%3E%20%22umodi2n%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22subii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22addii%22%3B%0A%22halfgcdii%22%20
> -%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22shifti%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22expi%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulT%22%20-%3E%20%22addii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulT%22%20-%3E%20%22negi%22%20-%3E%20%22mpneg%22%20-%3E%20%22leafcopy%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulT%22%20-%3E%20%22negi%22%20-%3E%20%22mpneg%22%20-%3E%20%22togglesign%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulT%22%20-%3E%20%22subii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-
> %3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulT%22%20-%3E%20%22mkcol2%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulT%22%20-%3E%20%22mkmat2%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22lastq%22%20-%3E%20%22pari_err_BUG%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22lastq%22%20-%3E%20%22equali1%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22lastq%22%20-%3E%20%22subiu%22%20-%3E%20%22subui%22%20-%3E%20%22addui_sign%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22lastq%22%20-%3E%20%22subiu%22%20-%3E%20%22togglesign%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E
> %20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22lastq%22%20-%3E%20%22divii%22%20-%3E%20%22dvmdii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqi%22%20-%3E%20%22mulii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqi%22%20-%3E%20%22addii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqi%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqi%22%20-%3E%20%22subii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqi%22%20-%3E%20%22mkcol2%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%2
> 0-%3E%20%22cmpiu%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22subiu%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqab%22%20-%3E%20%22mulii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqab%22%20-%3E%20%22subii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22mulqab%22%20-%3E%20%22mulq%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22FIXUP1%22%20-%3E%20%22FIXUP0%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22dvmdii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22mulq%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%
> 22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22uexpi%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22ZM2_mul%22%20-%3E%20%22mulii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22ZM2_mul%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22ZM2_mul%22%20-%3E%20%22addii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22ZM2_mul%22%20-%3E%20%22mkcol2%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD%22%20-%3E%20%22HGCD_split%22%20-%3E%20%22ZM2_mul%22%20-%3E%20%22subii%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22HGCD0%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22mkmat22%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22mkvec3%22%3B%0A%22halfgcdii%22%20-%3E%20%22HGCD0%22%20-%3E%20%22negi%22%3B%0A%22halfg
> cdii%22%20-%3E%20%22dvmdii%22%3B%0A%22halfgcdii%22%20-%3E%20%22mulq%22%3B%0A%22halfgcdii%22%20-%3E%20%22sqri%22%20-%3E%20%22sqrispec%22%20-%3E%20%22sqru%22%20-%3E%20%22uutoi%22%3B%0A%22halfgcdii%22%20-%3E%20%22sqri%22%20-%3E%20%22sqrispec%22%20-%3E%20%22cgeti%22%3B%0A%22halfgcdii%22%20-%3E%20%22sqri%22%20-%3E%20%22sqrispec%22%20-%3E%20%22__gmpn_sqr%22%3B%0A%22__gmpn_sqr%22%20%5Bstyle%3Ddashed%5D%3B%0A%22halfgcdii%22%20-%3E%20%22ZM_inv2%22%20-%3E%20%22signdet%22%3B%0A%22halfgcdii%22%20-%3E%20%22ZM_inv2%22%20-%3E%20%22negi%22%3B%0A%22halfgcdii%22%20-%3E%20%22ZM_inv2%22%20-%3E%20%22mkmat22%22%3B%0A%22halfgcdii%22%20-%3E%20%22mkcol2%22%3B%0A%22halfgcdii%22%20-%3E%20%22mkvec2%22%20-%3E%20%22cgetg%22%3B%0A%22halfgcdii%22%20-%3E%20%22gerepilecopy%22%3B%0A%7D%0A