# Error when calling the CRT function

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 close merge delete

Sort by » oldest newest most voted

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...

more