Skip to Content.
Sympa Menu

cado-nfs - Re: [cado-nfs] Can using multiple factor bases be used for computing discrete logarithm faster ?

Subject: Discussion related to cado-nfs

List archive

Re: [cado-nfs] Can using multiple factor bases be used for computing discrete logarithm faster ?


Chronological Thread 
  • From: Laël Cellier <lael.cellier@laposte.net>
  • To: Pierrick Gaudry <pierrick.gaudry@loria.fr>
  • Cc: cado-nfs@inria.fr
  • Subject: Re: [cado-nfs] Can using multiple factor bases be used for computing discrete logarithm faster ?
  • Date: Mon, 25 Nov 2024 09:39:58 +0100
  • Authentication-results: mail2-smtp-roc.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-1701.laposte.net
  • Ironport-data: A9a23:OR6mKqy0OlTcBuN01It6t+eEwirEfRIJ4+MujC+fZmUNrF6WrkVTn GYcUGGGM6yNMTPzLYx/PNm+oUkDuJGHnYdiGlRoqFhgHilAwSbnLYTAfx2oZ0t+DeWaERk5t 51GAjXkBJppJpMJjk71atANlVEliefSAOCU5NfsYkhZXRVjRDoqlSVtkus4hp8AqdWiCmthg /uryyHkEAHjgmQc3l48sfrZ9Eo25qiq4lv0g3RnDRx1lA+G/5UqJMlHTU2BByOQapVZGOe8W 9HCwNmRlo8O10pF5nuNy94XQ2VSKlLgFVDmZkl+B8BOtiN/Shkaic7XAhazhXB/0F1ll/gpo DlEWAfZpQ0BZsUgk8xFO/VU/r0X0QSrN9YrLFDm2fF/wXEqfFPlhOhEKkRrLLcVxessHF9D1 9U2dRwSO0Xra+KemNpXS8F3g9g7ac72IIwYu3dviGiGVa9gRZnbRL7W6Jle0StYasJmRKiGI ZtDL2M1MFKRMnWjOX9PYH46tOOhi325eDBcrFOYv4Iz6nDU1xB8lr7gLLI5f/TTFJgIwRrG/ D6uE2LRWBYoKfyf6zG86lGhv7/OphzcSbIXLejtnhJtqAbJnjNOUEd+uUGAifKwhkn7XdxEA 1cF/zIn66k07k2iCNfnNyBUu1afuwIEHt1ND+I96QeCj/OLu1/fAmEcSSVdZZogudNeqSEWO kGhlpT0Lxpq7ayvRE2QraqqoBGbF3U5MjpXDcMbdjct797mqYA1qxvASNd/DaK45uEZ/xmtn lhmSwBj190uYd436kmtwbzQqxyWzqUloyYu4xnPG2W48gx+ZYiqItX3sQGd6f9YK52FQx+Hs WRsdymiAAImU8/leM+lGbtl8FSVCxCtbGa0bblHQ8BJythV0yT/Fb28GRknTKuTDu4KeCXyf GjYsh5L6ZlYMROCNPAsOd7uUJx6kfG/SbwJs8w4iPIQOPCdkyfZp0lTibK4hjiy+KTRuf5lZ cvLGSpSJSpEWf8PIMWKqxc1iuVzmX1mnws/tLjkyA6j3b6fYnPdUr5tDbd9Rr5R0U9wmy2Mq 4w3H5LTk313CbSiCgGJq9J7BQ5RdxATW8upw/G7g8bfeGKK7kl9UaeJmdvMuuVNw8xoqws/1 ijnCxUCkQWl1SavxMfjQikLVY4DlK1X9RoTVRHA937xhxDPuK72tP5DJagkN6Iq7vJixvNSR vwIMZfISPdWRziNv3xXYZDhpcYwPF6mlCCfDRqDOTIfRp9HQxCW29nGegC0yjICIBDqvuQDo pqh9Djhf7w9eypYAv37Usmfl2GKgSBFmcZZfVf5Hd1ISUC9rKloM3PQi9E0EeEtKDLC5CCr5 yyICkwioc3I/os52/jSpKW+t4zyOfBPLklbOGj67LiNKijR+FS487JASOqleTP8Vnv+3qepd cF57qjbG+Jeunpkv65XMadZ/Yhn6/TB/7ZlnxlZRlPVZFGVO5ZcC3ih3/gXkJZSx7Vc6DCEa mjW9vZ0Yby2ad7YSngPLw8Yb8OG5/Eeuh/Wyd8XeEzaxitGzICrYHVoHSunqXJideNuEYYf3 +0eltYc6FW/hjoUI9+2tH1o2FrWHEMQcZcMl888O5DquDoJ21sZQJ37Cw3K2r+tRehIEHEXJ m6zuPKfqZVanlHPYlgiJ0jrhOB9v6kDiDpO7V0FJmmKpOb7u+8K7EVv1gozHytozURh8uNsO 2JUGVV/CoeQ8hxJ2sVSfWCeNDtQJR+e+0be5UQDz0uBfXL1S179FWwZEsSO9XA/7GhzUGV6/ raZ6WC9ShfsXpj78RUTUH5fic7IbIJO5DyZvfu4DuK5EIIcXQP1spSxZGENlQTrMfkxiGLDu +Nu2uR6Mo//CgI9vIw5DNO8+YkLaRXZOlFHf+5tzJkJEU7YZju2/zqEcGK1W8FVIs314V2KM NNvKu1PRiaB+n639B5DPpE1IphwgPINz/gBcOmyJWc57p2ungAwu5fUriXDlGsnRut1qvkEK 6TTSimjF1KBjn4Fik7Pq8h5YlCDW+cmXzGl/u6J87QuLakh4cVMakA514Wms0qFaDVH+w2mh yKdRqv04dE796FSsdrNKJhTPyS1NtL5a8qQ+i+RrdllTI3CIOXOhSwvu3jlOAVdZ+JJUP8ui 7i9itj9hkfYjqduQ0bLsomlErlJ7urjTuZ4D9/9KUcCvCqdWf3D5wkI1HC4JKdozvJcxJiDb CmpZPSgceU6X49m+0RUTCxFSTAPJr/SbJq8gQ+A99GyUgM81y7DJ/OZrU7ZV3lRLHI0CsevG z3KtOaLzfEGioZ1XTsvJexsWr18K3/dAZoWTcX772SkPzP5k2G5m+XQkDQ74mv2EViCKsHx5 KzFSjXYdBifvKLpzslTg7dtvy84XWpMvu0tQn0zo9JGqSi2LGojH9QvNZ8rDpJ1kCur8LraY DrLTnUpCASjfDBiXCj/3u/eXVakNrRTAuv6Gz0nwRrFIWP+ToaNG6Bo+Spc8m97MGmrhv2uL dYFvGb8JF6ty5VuXvwe/eG/nfwh/P7B23YU4gropqQe2frF7WkijxSN3TahVBAr1+nWkVnTY G8oWW9DQUe0DBeuSZ8mf3dNHwoFsXXpwilAgeJjBjrAk93z8QGC4KSX1yLPPnkraM0SI6USS DXxSnflD6W+xCkIoaVw0z42qfYcNB9Id/RW6IfnTBUVhL29rGIqI6vuWMbJoN4KoGZiLr8Wq tVgD7XSyqhIxIC9FYB6ETk0xq8=
  • Ironport-hdrordr: A9a23:HYL0Mq78mVBBQHPzCQPXwFTXdLJyesId70hD6qm+c20yTiXqrb HUoB19726LtN9xYgBepTnkAtjwfZqyz+8X3WGOVY3SITUO1FHYVL2KqLGSvwEIeBeOlNK1t5 0BT0EWMrSZZzlHZITBkXCF+r0bsb26Gc6T9IDjJjtWPGRXgtpbnn1EIzfeF1RwAA1PBZ84E5 T03KZ6jgvlfG0RKt6jDn0BU/fOorTw+q7OUFoCHhli8hCHiSih9b78HXGjsSs2YndKybcmtW fElhH0/ajLiZrX9iPh
  • Ironport-phdr: A9a23:BkhMChTZ03nqrxc8pgctOO0HUdpsonqVAWYlg6HPa5pwe6iut67vI FbYra00ygOSBMOHt7kd0bKe8/i5HzBbudDZ6DFKWacPfiFGoP1VpTBoONSCB0z/IayiRA0BN +MGamVY+WqmO1NeAsf0ag6aiHSz6TkPBke3blItdaz6FYHIksu4yf259YHNbAVUnjq9Zq55I AmroQnLucQbj5ZuJrw+xxbGrXdEZvpayX91Ll6Xgxrw+9288ZFt/ihMof4t69JMXaDndKkkU LJUCygrPG8y6MD3rxfPSheB6GUBWWsMiBpIBAbF7BD+Xpjvtybxq/Rw1iqHM8DoVL44QTut4 btlRx/ukycHKiU28HrLhcxqjaJUuwyuqhpiyIPJeo6VNf5+fqTAfdMGQGdKQ8hcWzBdDo66c oACFPQKM/pGoIbhplsOtRq+CheqBOPz0T9Dm3v60bQn3+g9DQ3K2QotFM8MvnvJttX4LKQcX +66w6bG0DvNce1b2Tn95obSah4uo+2DU71rfMrN0EkiDR/JgkmNpYHnOT6ey+QDs3Kc7+plT e+hjXQorB11ojOy2MojlI3JhoYUyl/a7yVy3YE4JdmiR0FlZd6oCodfuD+eN4tyQ8MtXXtot T0+yrIcoZ67ezMKyIg5yBLFbfyIbZSI7wvlWe2MLjh2mGhrd6ijhxau70eg0Ov8W9G03lpWs iZIjtfCum0N2hHN5MaLVPpw80W91DuR2Q3e9/9JLE8qmaffN5Ivwr89moQPvUrDHSL7hln7g auWeEgm/OWj9urpYrLjppCGNo90jBnzPb40ms2wAOQ4LBICX2+B+eSz0rDo4E73QK1Sg/Erk 6TVrIrWKMAFqqKjHgNZzIku5wy7AjqiyNgVnmcLIEhEdR+GlYTlJVDDLOrlAfq7h1mhlipgy u7CPr38GZXNMmbMkK38c7Z86k9T1hI+wcxZ6plJEL8OOujzVVX0tNHADh82LQi0w+H/BdVm0 4MeRXqPDraeMKPPrV+I6eUvI+iKZI8aoTrxNvoo6+LzgXMjnV8SZ7Gp3ZwMaHCkAPtqOUOZb mTwgtsZEGcKuBQxTPDyhVGfUDNfe2y+UqYi6j0hFY6qE4jOSpqpjbGFxCu7G4dZZmFCClCCC 3focICEVu8IaC2IPMBhliYIWqS/RI8l0RGutRH1y6B8I+rQ4CIYrZXj1MNp5+LNjx0y8yJ7D 9iF32GLVG57hnkISCMu3KBjvUx9zU+O3bVgj/xCCdNT/+9JUhs9NZPE0+N1Ec39WgXYctePR lamWc6rASoxT9I0298BeVxxG9SkjhDZ3iqlGaUZl7KRBM98zqWJ53n8Pdx8wHWO+6A8g0M3C p9XNGC8nK909E7cDpPFiVSxk6GwdK1a0jSbp0mZym/bmEjbVEZbXKHBXH0FLh/SpNn9oEjPS 7uvBK4PNgJZztWeJ+1MZ8G/3gYOf+vqJNmLOzH5oGy3Hxvdg+rUNOICGk0Y1STZUg0flhwLu GyBPk44DzugpGTXCHpvE0juagXi67o2s2u1G2kzyQzCdEh9z/yt4BdAgfWRT7UY07YAuSo7g zF9BFGmw9+QDdec9EJ6ZKsJWdom+x9c0H7B8Ql0P5iuNadn01oXfgAxtE7q0xR6EK1EmNAtt 28nigx/NfHQy0tPIhWf2524IbjLMi/y8RSoPrbRwU3b2c2K970n8/EksxDkoR2mEUsk/DA+j IEMlX+V/pLREAdUV5/tOqou3z59obySIiw05oeOkGZpLbHxqDjJndQgGOoizB+kOdZZKqKNU gHoQYUcAIC1JeomlkLMDFpMNf1O9KMyI8KtdueXkK+tMuF6mTu6jGNBqIlj20OI/iB4R6bGx ZEAi/2f2wKGUX/7gjLD+ojzkI1AIzofGm6+xDLMAIdJYbZucMANBHvva8y7y9NihoL8DmZC/ Q3GZRtO08uodByOKl3liFQOjQJG+zr+w3f+nm0n9lNh5rCS1yHP3en4IR8OO2oRAXJnkU+pO 4+/ydYTQEmvaQEt0hqj/0fzgaZB98EdZyHeR1lFey/uIiRsSKy14/CGasNLrpgltSFWXf6UZ VmCTaXhrl0c3j+pTA48jHgrMiqnvJn0hUkwjGuQKDB4oX7deMxq7RPW/NvHWfMX2DcaDnod6 3GfFh23ON+n+s+RnpHIv7WlVm6vYZZUdDHi0YKKsCbTCXRCORSkhLjzn9TmFVJ/yirnz5xwU i6Oqh/gY47t3qD8MOR9f0AuCkWuo8Z9H4h/lMM3ivRykTAej5iRu3EKlWPyPM9z3avma2ERS HgNzsKd7AX+2UJlJ26E3MqgCC3bk5EnPoPmJDJHkismiqICQL+Z9rlFgTd4rhKjoATdbOI81 jYRxP0y6WIL1uQAuQ4j1CKYUfgZGUhVOzCplgzdto7m6vQNIj/1Lf7hhRkb/5jpFryJrwBCV Wysf54jGXU19cBjKBfW13a17Ij4ed7WZNZVtxuOkh6GgfIGTfB53vcMmydjPnrw+HM/zOtux xhn0JX8t4WDL2Rg5oq9CwZfLSH4IcUe5nu+6MQW1tbTxI2pEph7T38PVZbsC/mlFDYTuO7PM w+WFyYgpzGdFKaVTmr9oA926nnIFZ6sLXSeInIUmM5jSBeqL0tamAkIXT8+k81xBkWwycfma ks8+iEJ6wuytE5X0uwxfUqaMC+XtEKyZzwzUpTaMBdG8lQI+RLOKcLHpuNrQ3MBoMXn/VbLc zbHIVoUSjtXECRoHnjFOb+jrZnF+umcXK+lKufWJK+JoqpYXuuJwpSm1s1n+SyNP4OBJCsqC fpzwUdFUX1jfqaR0zwSVywakT7MZM+HtV+9/CNwtMW27PXsXkrm+4KOD7JYNdgn9QqxhO+PM OuZhSAxLjg9tNtE3XjT1L0Wx0IfkQl1ciW1VLMdqSHKTaTf3/YIV0ddbyprM9BU4uQ60xUMc c/Xh9Xp16Jp2/44D1AWMD6p0sqtZMEMPyS8LAaeWh7NZe7AfGeXhZCmMsbeAfVKge5ZtgO9o 2OeGk7nZHGYkiXxEgqoOqdKhT2aOxpXvMe8dAxsAC7tVoGDCFXzPdlpgDkx2bBxiGnNMDtWN TFxdwVGo7mU7C5CqvF2A2ta8ncjK+SY0XX8jaGQOtMNvP1nDz4h3fpd+2g/wqBJ4TtsX/lpg G7Vs8JhpFCgnazWlWI+Fh5HsjFQmI/Nu0h+c/a8lNEISTPP+xQD6n+VAhIBqo5+C9HhjKtXz 8DGiKP5LDoqGzP85s4AH43TNd6IN3snPl+wR2aNSg8MVTmwKWyZgUFBwqn6Hpi9qpEirYPwl dwIR6MJDDTd+dseA1xiB8APZpF6QmF9+YM=
  • Ironport-sdr: 674437e0_ubMfrB0BZ737WaLMPwui9LG4dxnclTLksjbY/0gfdhjCDlp 7geSDUF6+QOGHwXLFt4GMt/1wfD8g2sVjPylftw==

Hi,

They claim to be 30× faster than the naïve index calculus method at 70bits and explain why a bit.

then can the underlying idea be applied to completely different scenarios ? I was thinking about some non effcient index calculus algorithm on elliptic curves ?

Cordialement,

Le 25/11/2024 à 08:02, Pierrick Gaudry a écrit :
Hi Laël,

I didn't know this paper. I had a quick look. Here are my thoughts:

- this is an L(1/2) algorithm, while NFS is an L(1/3) algorithm.
Asymptotically, this can not win against NFS. The crossover depends on
implementations, but usually it is around 100 digits inputs.
- the improve the individual logarithm step, which is the less costly
among all the steps.
- actually, I am not sure this is a real improvement compared to the
naive approach.
- the individual logarithm step is different in NFS, so that the
technique can not be transposed to this algorithm.

To conclude: I might be wrong (of course), but I don't think this has any
chance to be interesting for large scale computations.

Regards,
Pierrick

On Sun, Nov 24, 2024 at 04:59:32PM +0100, Laël Cellier wrote:
Bonjour,

I was reading this paper : https://arxiv.org/pdf/2409.08784. Although it
contains rants and the timings are questionable unless they only have their
phones, the underying idea is to pick up several factor bases instead of 1
in order to shrink the number of individual discrete logarithms for a given
target.

Now, I’m only a beginner, but is this an idea that can be useful for more
advanced algorithms ? They give full step by step of their textbook
algorithm.

Cordialement,





Archive powered by MHonArc 2.6.19+.

Top of Page