Skip to Content.
Sympa Menu

cado-nfs - [cado-nfs] In finite fields of medium characteristics, what does prevent shrinking the field size of even degrees down to their larger order in order to solve discrete logarithms ?

Subject: Discussion related to cado-nfs

List archive

[cado-nfs] In finite fields of medium characteristics, what does prevent shrinking the field size of even degrees down to their larger order in order to solve discrete logarithms ?


Chronological Thread 
  • From: Laël Cellier <lael.cellier@laposte.net>
  • To: cado-nfs@inria.fr
  • Subject: [cado-nfs] In finite fields of medium characteristics, what does prevent shrinking the field size of even degrees down to their larger order in order to solve discrete logarithms ?
  • Date: Sat, 30 Nov 2024 10:19:22 +0100
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=lael.cellier@laposte.net; spf=Pass smtp.mailfrom=lael.cellier@laposte.net; spf=None smtp.helo=postmaster@smtp-outgoing-1703.laposte.net
  • Ironport-data: A9a23:nIJqRqhNdPjTHz8KRdta/19RX1610xQKZh0ujC45NGQN5FlHY01je htvW2uAbP6NMTfxfdklbYWw9RxTuZSDmIM2SQBvqy1nQihjpJueD7x1DG+gZnLIdpWroGFPt phFNIGYdKjYaleG+39B55C49SEUOZmgH+a6UqieUsxIbVcMYD87jh5+kPIOjIdtgNyoayuAo tqaT/f3YTdJ4BYqdDtOg06/gEk35qir4WhA5gVWic1j5TcyqVFFVPrzGonqdxMUcqEMdsamS uDKyq2O/2+x13/B3fv4+lpTWhRiro/6ZWBiuFIOM0SRqkQqShgJ70oOHKF0hXG7JNm+t4sZJ N1l7fRcQOqyV0HGsLx1vxJwS0mSMUDakVNuzLfWXcG7liX7n3XQL/pGMEwPAI03vcRLJHhC1 +5AISs9Uh+emLfjqF67YrEEasULN8z3JMYYp21vyjDfArN/HsiYBaHD/dhDwDp2gM1SdRrcT 5NHMXw+NlKZOUEJYw9OYH49tL/Aan3XdzRVrBSeqK4z4mXJ5Ah4yL/2LNeTfNGWLSlQth/A/ TqbozqpWHn2MvTPlwOlzV2IutTmwzrBU78CBuah39x11Qj7Kms7U0dOCgbj+5FVkHWWUNtTL AkS9DEGtrk37EXtT9/nXhT+rmTsg/IHc8FVD/V/7xyRxa3V5QncXzdcFXhFYcQhr9M7Azony jdlgu8FGxRTvYSoSV3a1IuxtD+QK3AcNl8+ajIbGF5tD8bYnKk/iRfGT9BGGaGzj8HoFTyY/ 9xshHVl71n0pZNXv5hX7Wz6bySQSo/hYDRd2+k6dnmg8hs8Y5O5aIup71eetKkYd8CdR0GGp 2QJ3c6T8Iji7K1hdgTTEY3h/5nwuZ5p1QEwZ3YzRvHNEBzxoxaekXh4um0WGauQGp9slcXVS EHSoxhNw5RYIWGna6R6C6roVJ9wnPC9TYS1CqyLBjarXnSXXFHelM2JTRDKt10BbGB1yf5X1 WqzLpzwUSZy5VpPkGToGo/xLoPHNghlnzuMGMihp/hW+aWZfnqZTbYDPROVZ4gEAFCs/m3oH yJkH5LSkX13CbSmCgGOqNJ7BQ5QcRATW8usw+QJLbHrH+aTMD17YxMn6e97I9Q990mU/8+Ul kyAtrhwkQKg2yKfeFXWNxiOqtrHBP5CkJ7yBgR0VX7A5pTpSd3HAH43LsNuIesU56Z4wORqT vIIXcyFD74dAn7E4jkRJ9215oBraB3h10rEMjuHcQoPWcdqZzXI3dv4ISrp1i0FVRSsueUE/ raP6wL8QLg4fTpEMvr4UvyV8g6OjSAvo94qB0rsCftPSXro67lvenDQjOdoAsQiKifj5zq91 iSNMCcyu+KWmYsR9YTNiYultKasKfN1RWBBLlnY7JG3FCjUxXWiyol+S9S1fSjReWf32ae6b 8NXxOHYHNxeu31V6qxQPbpP5oAv1evF/rN14FxtIyTWUg6NFLhlHEij4eBOka98nplipgq8X xO0yOlwYLmmFpvsLw8MGVADcO+G6PAznwvS59QTJGHRxnd+3JiDYHVoEyi8sg5vB5orD9p92 sYkgtAc1CKngBlzMtqmsDFdx17RElM+CZcYprMoK661rDE0y2NyQ43WUQ73x5CtV+9iEGcXJ h2sua6ToIgEm2TjdSIoGGnvzNhto80EmCp3wW8oI3WLndv4hcEL4iBBzARvTipp40VG98lRJ llUM1ZEIPTS3jVw2+lGcWOeOyBAIxy76EbB8UQtqzyAQ2akSGXycWsZBcvW2Ww87mhzUCdRp 5fA+l24TATaRcDV9QkxUH5DtPbMY4FQ9ArDucb/BOWDPcAwTgTEi5+UR1gjikXYE/JqoXbYt M9W8/1WVZTrBRUPoqY+NZaW5Y4QRD+AOmZGZ/Nrp4ENIk3xZxCw3mKoB32qW8YQOcHPz1C0O /ZuKu1LSR668iSE9RIfJKwUJo5LjOwb38UDdpzrNFw5neOm9BQxi63p9w/6mGMPaPdtm5xkK oruKhSzIlbJjn5Qw2LwvM1IP1SjWuY9ZSr+4fuU9dsYHJdSocBudkAPioGPhUu3Czc+3Ryov 1LkXZT0nshC0oVnmrX+HppTXzuULczBb8XW0QSRnekXU/bxH5bvjS03pGPjHTxqBpoKetEul b2yoN/9h0zEm7AtUlHmoZqKFogXxMCiXOF4Y9D7A0RHly68AO7t/Box1GSqIrNZkN5mx5eGR inpTOCSZNIqS9Nm63kNUBdnEjEZEP7RfIr7gCGA89CgN0A471TcDdWF8XTJUzlqRhUQMcejN j6u6uec2N9Iia9tWjkGPqhCKL1lKgbBXaAGSYXAhQOABDP1vmLY66rQrjt+2zTlEXLeLd3b5 6jCTR3AdBifnqHE4dVako5qtC0sE3dPrrgsT30Z5uJJpWi2PEweIcQZFKc2OJVevyjx9ZP/P RXmTm8pDwfjVjVlLzT4xvneXTmkO+9fAeehewQV/H6VZRnvVcnESPFk+zx76nh7Rir7wav1Y ZsC83n3JV6qzosvWe8X4eehjPx6wu/BgEgF4l35j9e4FiN27W/mD5C9NFElue37/8DxeIHjP m0pXSVDXV20Tk/3HoM5JCYOXhUQpDT00zhuayqTqDoaV0N308UYoMAT+cmqulHAUCjODLoHX XTsW2bL5W2KspDWkbV8oMon2MeYFtrSdvVX78bfqck6m6io7X87MoUEkDZnoATOPuJAOwu1q wRAKETSyKhIxI69FVFWJcg0F0pNb08x
  • Ironport-hdrordr: A9a23:l/dCwqiI4moXI6oALLkiNOt8V3BQXi4ji2hC6mlwRA09TyXqrb HIoB1773/JYVMqKQwdcL+7Scu9qe21z+8O3WB8B8baYOCEghrMEGgB1/qA/9SIIUSXnI9gPM xbAtBD4bPLfD5HZIrBkW2F+q0bsaK62ZHtgP7Yi3NkTQRrbK8I1WtEIzfeF1RwABNeDZ49GI WR46N8yQaISDATd8P+HGAMW/PKut3NmvvdDiIuNloi4AmKyTyp7aP3CBXw5Hxybw9y
  • Ironport-phdr: A9a23:/gHVshPNZM0vhlWVeZEl6nY5BxdPi9zP1u491JMrhvp0f7i5+Ny6Z QqDvqwr0QKBHd2Cra4f06yO6+GocFdDyKjCmUhBSqAEbwUCh8QSkl5oK+++Imq/EsTXaTcnF t9JTl5v8iLzG0FUHMHjew+a+SXqvnYdFRrlKAV6OPn+FJLMgMSrzeCy/IDYbxlViDanbr5/I gi6oR/Ru8QWnIBuLro9xgbTrnZHdela2XlkKU6Pkxr5+8y94INt/yNMtv0u8MJNTb/0c6MkQ 7JGET8oKXo15MrltRnCSQuA+H4RWXgInxRLHgbI8gj0Uo/+vSXmuOV93jKaPdDtQrAvRTui9 aZrRwT2hyoBKjU07XvYis10jKJcvRKhuxlyyJPabY2JKPZzeL7WcNUHTmRDQ8lRTTRMDZ+/Y YUBAOUOM/hWoYngqVUUtRWzHhOjCP/1xzJSmnP6wK833uI8Gg/GxgwgGNcOvWzSotrvKKASV f2+wbfWwjXHa/NW2Cny6JLVeR0mpfGDR6x/cc7LxUYzCQzFilGQqY37MDOPzekNt3KU7/JnV eK0l24otRt9oj6xyccwk4TEgJ8exV/Y+ytj2ok1OcG4R1BhYd6iCJZduCOXOoh0T84tTG9lu js2x7kHtJC0fyUG1ZsqyhHdZvKJc4aG7R3uWPqPLDl3mX5rd7yxiRi2/Eauy+DxUtW53VBXp SRLldnMs2oC1x3V6sWfUPR95Eig2TeR1wzJ7eFEO080mKzGIJAi2r49jocfvEXfEiPsnEj6k rWaelg69uWn8ejrf6nqqoKEO4J3lA3yKKUjl82lDegmMwUCRXWX9OC42bDl4Eb0XrFKjuAtk qnFrp/aP9kVpq+4AgBLyosv9xCyBCq83tsCh3kINldFdQqHj4f3P1HOJ+j1Dey6g1SwiDdn3 vfGPqD9ApXCKXjDkbHhfblk50JBygc/0d5S64hQCr4bOPLzXVTxtMDGARMjNQy73frnBM181 oMYR22PHreUPL7TvFOU/O4iJ/eAaJUItDrjJPUp/ePigWMklVMFeKmmx5oXaHS2HvR8JEWZZ GLhgtMbHmgUugoyVvDlh0OGUT5XZna9Qbg86yo/CI28FYfDQZutgKCf0yuhGJ1ZeHxGBkiKE Xjzb4qEQesDaDqOIs99lTwJTaWtR5c71R6yrA/616ZnLu3M9yIEr53syd916/TVlRE87jx5F N+d0mGIT2FshGwEXT423KZloUx80FiPy6Z4g+YLXeBUsvhAXgB/M5DH5+18EdH7HAzbLfmTT 1PzZtwlBXkaQ9Y1wtIUKxJ5EtimyBvO2y6rDqU9k7WTA4co/+Ta0mSndJU18GrPyKR01wpue cBIL2Dz3saXliDWDo/NyACCkrqyML8bxGjL/XuCymyHuAdZVhRxWOPLRyNXfVPY+PL+4E6KV LqyEfI/KAIUzcePLu1BZ9ntjFhcbPPqINPFf2/3nWqsVl6T3r3ZVIPxYC0G2TnFTk0NkgQd5 3GDYAw3CyPnqG/aCD1jD3rralvr6vVz7nW2Uhx81BmEOmtm0bf94RsJnbqcRvcUi6oDozsko i5oEUyVxNfKE5+HuhZue6RabpZkvw8ck2bQrwtmIpHmKa1+7rIHWyJwuU6mlxB+C4Eb1NMvs Gtv1w1qb6SRzFJGcTqcm5H2ILzebGforlipbObN11fS3czzmO9H4ekkq1jloACiF1Yzu3Rh3 d5P1nKA55LMRAMMWJP1W0wz+lB0vbbfKiU64orV0zVrP8zW+nfG0t8tQuAozhKhcs13NKqcE xTuHoscCtTvYO0mll61bw4VafhI/f1RXYvufP+H1ai3eed4yWv41SIWusYkiB7KrnIlGYuql 94fzvqV3xWKTWL5hVal6YXsnJxcICoVBiy5wDTlA4hYYutze5wKACGgOZ7SpJ02ipjzVnpf7 FPmCUkB3ZrjfROfaxr20AlU1EkNiXiugSyj0zEylTw15Pn6vmSG06H5eRwLN3QeDm1rgFOqK oWwi9EXRmCsZhAujweoo0D32+IIwcY3Z3mWSkBOcS/sKmhkWablrbuObflE75YwuDlWWuCxC byDYob0uABSkybqHm8FgSs+aynvoZLh2RpzlGOaKn936nvfY8B5gxnFtpTQQvtY3zxOQycd6 3GfAlGxO5+i8NGQlprZmuS3T2W6SpAVdyT3hY+Nryq042R2DAb3xq7r3Iy9V1FgjWmij4AiX D6tzl60eoTx0qWmLe9rNlJlAlPx8YsyG41zlJcxmIBF3HEbgpuP+n9U9AW7ed5f2K/4cD8MX WtSnYaTsVKjgRc/aCvRntGcND3V2MZqatikb3lD3ys865sPE6KI9PlfmjMzpFOkrAXXaPw7n zEHyPJo5mRJ5oNB8Acr0CiZBagfWEdCOim53RCB4tT4p6hTYGeia5C03VJ5hsysSrePvksPP RSxModnBiJ24shlZRjI2XD3rIrpfN3RYMg7shSMlAzcgq5TJY57xZ9ozWJ3fGn6u3Mi0esyi xdjiIq7sIawIGJo5KulAxRcO269d4YJ9zrql6obgteO0tXlAMB6AjtSFsiNL7rgAHcIuP/gL QrLDDAstiLRB+/EBQHGoEZ+8yCWTcjtZivRfSNFi4s+A0PDbiSzmSgyWzM31t48HwGun4n6d VthoysW/hj+owdNzeRhM1/+VH3erUGmcGV8Tp/XNxdQ4gxYgiWdecWD8uJ+GT1Z9Zy9vUSML GKcfQFBEWAOXASNGVniOrCk4dSI/fKfA6KyKP7HYLPGruI7Nb/A3ZW0zo5v5CqBLO2UO2V6S vomxkVEXHZ2Xp2Gw25JTyUPkDnRYoidqQv9six7o8aj8ej6DQLi4Yzcbtkaed5r+h2wneKCL 7vJ2n4/eGwej8lQgyaQket6vhZakSxlejizHK5VsCfMSPmVgapLF1sAbDs1MsJU7qU61w0LO MjBi9qz2KQr65x9Q1pDS1HlndmkIMIQJGToflfOCULNP7mCITzG2enzaLu7UqFdyuNZq1fj3 FTTW1+mJTmFmzTzAlq3NvpQiSiAIBFEkJq4bg4oDnX/Q9XnbBL+aYAv1nsyyKUznW/Hc2gRL XIvFiEF5q3V5iRejPJlHmVH5XcwNuiIlRGS6OzAI4oXu/9masybv+ZT+HMh17YT6ixYFqUdc Mr6tdtyuxShj/WAzTthX18X9W4QwoaCpUJ5Jaif8JRcCy6sFPcl6WyIDA8Wqp1jB8G948ht
  • Ironport-sdr: 674ad898_NgirX5P1DQfwtFGzDdUaN2lsa5/AkEXlVjEjeUYf16Sfdcq 7NginZd8YYL0HnGRSnabCnMZLuCtt+3oM7AR6KQ==

Hi,

In the recent years, several algorithms were proposed to leverage elliptic curves for lowering the degree of a finite field and thus allow to solve discrete logairthm modulo their largest suborder/subgroup instead of the original far larger finite field. https://arxiv.org/pdf/2206.10327 in part conduct a survey about those methods. Espescially since I don’t see why medium chararcteristics would be prone to fall in the trap being listed by the paper.

I do get the whole small characteristics alogrithms complexity makes those papers unsuitable for computing discrete logarithms in finite fields of large charateristics, but what does prevent applying the descent/even degree shrinking part to medium characteristics ?

Of course, a key problem is no implementation for solving discrete logarithms in finite fields of small characteristics in near polynomial time is public (feel free to correct me) and it would take an amount of effort to bring this to ᴄᴀᴅᴏ‑ɴꜰꜱ that I can’t provide due to lack of knowlwedge.

Sincerely,




Archive powered by MHonArc 2.6.19+.

Top of Page