How to use GF() on a very large finite field ?

asked 2024-07-16 12:13:12 +0200

updated 2024-07-16 20:39:03 +0200

As far I understand it correctly, GF(Integer) is used to declare a finite field which can for example be used for declaring an elliptic curve (this is what I want to do).
But why using a very large composite number (2 or 3 thousands bits long) like :

GF(12092909088188237225393433017559174875623137613219078327682045681675023350320878590139619158941453632724570634378148379186020109423506557278061404249513976103803771139954000579995199902828634263992330574392218791796266323480026479977659504287064359209036331389750395884727865805793574046154686347934603866375769645860851559671200189106819576945533990794197558448169154800495832790107673176422796675256499746815795625450299074794144048526198146639914021389804755241528331708078456200260597013666698340612446162656471808349941941036242500801205678881620332591272087635015318077794473705628671572713897714140224506269671672327501746902155512482220944778556374239955378577691861316356789180373125486706142640931817968722234080019888921817141837856053156323850750365255047978587780912486395587404967932864588640269696396456375831408999624015664858331115319294937654521467886227817728683577618500683880562054279134724944161)

seems to take too much time to feasible ? How to declare a dummy elliptic curve without using GF() ?

edit retag flag offensive close merge delete

Comments

Can you illustrate the issue with an actual code example?

Max Alekseyev ( 2024-07-16 19:48:01 +0200 )edit

@MaxAlekseyev Try GF(21009474928063398113313338499806248872571571764108368584252996789952845013853014160536610808644349474472134504631209689999545964246403529336179380298861735113891098638485928212345411326605632881575672338305940762732454501025792917352899639736241461707887589102522852127720327234747088233946875074034579490779512377473757703950604066218581435386956112097496825785846632390114239632275256574241126674182763406069083271758459150948975406620089712005871369207513121961087527948880273661561993809426056038877708299352499912208866945035695014244143863787419004009216626879942228771209111914942901229942921347317548992896519437446901028666053570779290986731489891231504242794982592992888914748952911550388794271123650020) it won’t complete

user2284570 ( 2024-07-16 20:16:20 +0200 )edit

The number in your comment is not a prime power, so GF(...) is not defined. Perhaps it doesn't complete because it's first trying to factor the number and that takes too long.

John Palmieri ( 2024-07-16 20:51:44 +0200 )edit

For a composite, which is not a prime power, one can try to work in the corresponding ring defined via Zmod().

Max Alekseyev ( 2024-07-16 22:25:32 +0200 )edit

add a comment

answered 2024-07-17 11:01:34 +0200

vdelecroix
7620 ●20 ●84 ●168 http://www.labri.fr/pe...

First of all, it would have been wise to give your number in factorized form. The problem seems to be that Sage tries to be "too" clever by choosing a canonical polynomial for the extension GF(p^12):GF(p). You can generate a random irreducible polynomial and build the extension by hand

sage: p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
sage: A = GF(p)
sage: B = A['x']
sage: poly = B.random_element(12, monic=True)
sage: while not poly.is_irreducible():
....:      poly = B.random_element(12, monic=True)
sage: C = A.extension(poly, 'u')
sage: C
Finite Field in u of size 21888242871839275222246405745257275088696311157297823662689037894645226208583^12

edit flag offensive delete link

add a comment

How to use GF() on a very large finite field ?

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

How to use GF() on a very large finite field ? edit

Comments

1 Answer

Your Answer

Question Tools

Stats

Related questions

How to use GF() on a very large finite field ?