Michael Thornvig Mikkelsen <mik@daimi.au.dk> writes:
> Rasmus Villemoes wrote:
>
>> Michael Thornvig Mikkelsen <mik@daimi.au.dk> writes:
>>
>> > Jeg skal bruge et irreducibelt element over GF(2) af grad 25, til at
>> > genere et legeme med 2^25 elementer. Jeg har ikke adgang til
>> > Mathematical eller lignende. Er der nogen "derude", som har et "på
>> > lager"?
>> >
>>
>> Ikke på lager, men Mathematica siger x^25 + x^22 + 1; ved en
>> google-søgning fandt jeg ikke umiddelbart brugbare tabeller.
>>
>
> Jeg har selv fundet en fremragende tabel i chapter 4 p 158-159 i
> nedenstående "online bog"
>
>
http://www.cacr.math.uwaterloo.ca/hac/
>
> meeen, det viser sig at jeg skal bruge et meget større legeme, end jeg
> først antog. Jeg skal bruge et irreducibelt polynomium over GF(2) af grad
> mindst 2^25, og det kan jeg ikke finde i ovenstående tabel. Desuden er
> det ønskværdigt at de led som ikke har højest grad, har grad mindre end
> 32 (og der skal selvfølgelig være så få led som muligt).
>
> Jeg ved ikke om Mathematica kan klare så store legemer?
>
Hmm, ja, der må siges at være forskel på 25 og 2^25. Min
google-søgning ledte mig frem til siden
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/trinom.html
som ikke helt opfylder dine krav. For det første er graden 'kun'
omkring 2^22 for det størst nævnte, og graden af det midterste led er
for de nævnte af størrelsesorden ~½·r; til gengæld er det så kun 3 led
i alle polynomierne. Grunden er nok, at polyomierne på siden er mere
end bare irreducible. Sidst i Examples-afsnittet står der
* From the known primitive trinomials of degree 6972593 (Bibury
and its reciprocal), we can deduce infinite families of
irreducible trinomials whose degrees are multiples of 2^6972593
- 1 .
men der står ikke hvordan man kan finde dem. Til gengæld er der et
link til programmet 'irred', som tilsyneladende kan lige præcis det du
har brug for. Ifølge Mathematica er det mindste primtal > 2^25
33554467, så det er nok den værdi for r du skal bruge. Jeg ved ikke om
programmet tager urimeligt lang tid for en så stor værdi, men det er
da værd at prøve.
Mvh Rasmus
--