Ask Your Question
0

Error when calling the CRT function

asked 2017-11-21 08:11:18 -0600

anonymous user

Anonymous

I have the following Magma code that I want to rewrite in Sage:

D := 1444451111007492249157225145240924628689936300289032719520989176681391983750\
5026233531541656521516385113467258658058158757413856041226225263754438069945819\
321862869928499936414339298248291015625;

N2tfac := [ 389017, 704969, 912673, 1030301, 1295029, 1442897, 2571353, 3307949,
3869893, 29929, 32761, 37249, 38809, 52441, 54289, 58081, 66049, 72361 ];

signs := [ 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1 ];

vecTau := [Integers()!(Sqrt(-IntegerRing(fac)!D)) : fac in N2tfac]; 

lst := [(-1)^(Integers()!signs[ind])*vecTau[ind] : ind in [1..#N2tfac]];

tau := CRT(lst, N2tfac);
"tau=",tau;

and when I run it I get the result of tau= 13374843322841533370163824183368767068675387448700309211897565319967356307\ 909512193392966464291429. But when I rewrite it in Sage as this:

D = 1444451111007492249157225145240924628689936300289032719520989176681391983750\
5026233531541656521516385113467258658058158757413856041226225263754438069945819\
321862869928499936414339298248291015625

N2tfac = [ 389017, 704969, 912673, 1030301, 1295029, 1442897, 2571353, 3307949,
3869893, 29929, 32761, 37249, 38809, 52441, 54289, 58081, 66049, 72361 ]

signs = [ 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1 ]

vecTau = [Zmod(fac)(-D).square_root() for fac in N2tfac]

lst = [(-1)^(signs[ind])*vecTau[ind] for ind in [0..len(N2tfac)-1]]

tau = CRT(lst, N2tfac)

It gives me an error message of:

TypeError: unsupported operand parent(s) for -: 'Ring of integers modulo 704969' and 'Ring of integers modulo 389017'

Any ideas what the problem might be, and how to solve it? For one thing I know that the sqrt function in Magma and Sage does not always return the same square root, can this be the problem? If yes, how to circumvent it, if no, what is causing the error here?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-11-21 10:38:17 -0600

B r u n o gravatar image

The problem is that the function CT does not accept elements from Zmod(N) as inputs, but integers from ZZ. So you need to convert elements from Zmod(N) to ZZ after taking the square root. The following works:

sage: D = 1444451111007492249157225145240924628689936300289032719520989176681391983750\
....: 5026233531541656521516385113467258658058158757413856041226225263754438069945819\
....: 321862869928499936414339298248291015625
sage: N2tfac = [ 389017, 704969, 912673, 1030301, 1295029, 1442897, 2571353, 3307949,
....: 3869893, 29929, 32761, 37249, 38809, 52441, 54289, 58081, 66049, 72361 ]
sage: signs = [ 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1 ]
sage: vecTau = [ZZ(Zmod(fac)(-D).square_root()) for fac in N2tfac]
sage: lst = [(-1)^signs[ind] * vecTau[ind] for ind in range(len(vecTau))]
sage: tau = CRT(lst, N2tfac)
sage: tau
13858224800908315507294199691824697464548122256842223727609336351240341959268664361050839245186599

Remark: It would certainly be sensible for CRT to accept modular elements...

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-11-21 08:11:18 -0600

Seen: 25 times

Last updated: Nov 21