Wikipedia:Reference desk/Archives/Mathematics/2024 August 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 27

How does solving the finite’s fields discrete logarithm is easier on an extension field than with a prime degree ?

Hi,

simple question, I’m seeing discrete logarithms records are higher when the finite’s field degree is composite and that such degrees are expressed as the degree of prime and the composite part being the extension of the field.
But how does that makes solving the discrete logarithm easier ? Is it only something that apply to index calculus methods like ꜰꜰꜱ or xɴꜰꜱ ? 2A01:E0A:401:A7C0:6861:5696:FAEB:61D1 (talk) 19:14, 27 August 2024 (UTC)

I believe the function field sieve has much better asymptotic complexity for large powers of primes than other methods. Not sure about compositeness of degrees. Tito Omburo (talk) 20:36, 27 August 2024 (UTC)

I’m also seeing it applies to variant of the ɴꜰꜱ. The paper about 2⁸⁰⁹ discrete logarithm record told the fact 809 was a prime power was a key difficulty. And indeed, all the larger records happened on extension fields (with a lower base prime exponent than 809)

The problem is I don’t understand how it’s achieved to make it little easier. 2A01:E0A:401:A7C0:6861:5696:FAEB:61D1 (talk) 05:02, 28 August 2024 (UTC)