Ask Your Question

whatever's profile - activity

2019-10-03 04:41:06 -0600 received badge  Popular Question (source)
2019-02-16 12:15:36 -0600 received badge  Notable Question (source)
2018-12-02 10:40:56 -0600 received badge  Popular Question (source)
2017-11-21 08:11:18 -0600 asked a question Error when calling the CRT function

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?

2017-11-21 05:27:38 -0600 received badge  Organizer (source)
2017-11-21 05:24:11 -0600 asked a question Sage code is not finishing the execution

I have the following Sage code:

proof.arithmetic(False)
N1 = 3800593520764213807714463070034888649702845066265551031357734876647057491457955294136255701171875
p = 351990877768566621413883883141886047350313637057
q = 3
N2t = 1
K = 1
qi = 61
B = 3940281
N2tfac = []
while N2t < K*2*N1*q:
    qi = next_prime(qi)
    # check that -q is a square mod qi
    Fqi = GF(qi) 
    while not -Fqi(q).is_square():
        qi = next_prime(qi)

    ei = min(floor(log(B, qi)), ceil(log(K*2*N1*q/N2t, qi)))
    N2t = N2t*qi^ei
    N2tfac = N2tfac + [qi^ei] # concatenate two lists

print "N2t =", N2t
print "N2tfac =", N2tfac

And I tried running it in Sage Notebook locally and running it through a VM, but in either case it does not finish with the execution, whereas the same code in Magma finishes immediately. Any ideas what the problem might be?

2017-11-21 05:17:20 -0600 commented answer Inconsistent result between Sage and Magma for sqrt

Yes, both return correct answers, no doubt about it. It was just that I was rewriting a Magma code in Sage, and I want to have consistency, and as you say satisfy the principle of least surprise.

2017-11-20 12:22:19 -0600 asked a question Factorization sequence to enumerated sequence in Sage

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

Eltseq(Random(FiniteField(2^8)));

This basically produces the following result: [ 0, 1, 0, 1, 1, 1, 0, 1 ]. The function Eltseqis defined as this in the documentation (https://magma.maths.usyd.edu.au/magma...):

Given a factorization sequence f, create the enumerated sequence containing the same pairs of primes and exponents.

Any ideas how can I rewrite this line in Sage?

2017-11-20 12:05:02 -0600 commented answer Inconsistent result between Sage and Magma for sqrt

Take this for example Zmod(23753)(-100), both sqrt and square_root return the same result, meaning the smallest valid value, that is 2244, whereas Magma returns 21509.

2017-11-20 10:00:04 -0600 commented question Inconsistent result between Sage and Magma for sqrt

Quite interesting. Using square_root actually produced the result that I want. Thank you. If you can provide it as an answer, I can accept.

2017-11-20 08:57:39 -0600 asked a question Inconsistent result between Sage and Magma for sqrt

I have the following Magma code:

N2t := 625;
D := 84100;
tau:= Sqrt(-IntegerRing(N2t)!D);
tau

It basically creates a ring of integers modulo 625, evaluated it for the value of D with negation, and finally applies a square root calculation. Now, the result produced is 280. When, I convert the code to Sage such as this:

N2t = 625
D = 84100
Z = Integers(N2t)
tau = sqrt(-Z(D))
tau

I get a result of 30. Any ideas why this is the case?

2017-11-20 07:06:32 -0600 commented answer Lattices in Sage

Thanks, this works, and using sqrt(D) for the original values given above, it produces the correct results.

2017-11-20 07:05:34 -0600 received badge  Commentator
2017-11-18 15:04:51 -0600 commented answer Lattices in Sage

You can use the online Magma calculator for the experimental purposes, it is more than enough: http://magma.maths.usyd.edu.au/calc/

As for the Magma code in my question. It will basically create a lattice of rank 2 and degree 2, which has basis:

( 457685173309633 -876887928958864)
( 953127960009412  657836416577629)

and Inner Product Matrix:

[1 0]
[0 53364935730486508893809772233249725927747397616650814998641]

So basically the second matrix is the inner product matrix. I hope this is more clear.

2017-11-18 12:37:31 -0600 commented answer Lattices in Sage

Your result will produce more or less correct results (just the sign will be wrong) if one matrix is used. But, in my case as you can see in the original question, there are two matrices used. I added some numeric examples to the original question, to see the contrast. Please note that there is another value called D.

2017-11-18 10:48:55 -0600 asked a question Convert sqrt to Integer or Rational

I have the following Sage code, but it fails whenever I try to coerce the sqrt to Integer, or convert to Rational.

# compute sqrt of -q modulo N2t
Z = Integers(N2t)
tau = Integer(sqrt(-Z(D))) #Rational(sqrt(-Z(D)))

# build matrix
M = Matrix( QQ, 2, 2,
        [ [ N2t, 0 ] ,
          [ tau, 1 ] , ] )

Any ideas how to solve the problem?

2017-11-16 08:22:29 -0600 commented answer Lattices in Sage

I think the main problem is not the LLL algorithm per se, but the used method here. If one creates the same matrix both in Sage and Magma and applies the LLL algorithm, the result is the same. But, in my example above, in Magma, a different method is used, which is called LLLBasisMatrix: https://magma.maths.usyd.edu.au/magma...

I think what I look for is whether Sage supports creating lattices, and if it has method similar to LLLBasisMatrix from Magma.

2017-11-15 16:30:30 -0600 commented question Lattices in Sage

@dan_fulea $L$ is supposed to be a lattice generated by two vectors $(N_2,0)$ and $(\tau,1)$. The Magma code is not written by me, I'm just trying to convert it to Sage, that's why I also don't know exactly the need of the second matrix in the lattice generation.

2017-11-15 16:22:41 -0600 commented answer Finite field with a big prime

@vdelecroix thanks for the shortcut!

2017-11-15 09:57:00 -0600 marked best answer Finite field with a big prime

I have a big prime, more specifically this:

256483255156361932417132258347642243836482531433703606100673566368701775984391074950755957740831302271726064361036532787555367784881743033151459679719384059441796909655754726931594235526089964299772527064444664849297946645448542084872468703531502916810392849103591863993942507123567447217707741049535609589556145772688829006027343782856882041313493735257675668705105470403029890335429696731280142666631433352362201684109344320318132052181715470800225241872816320269980127606041552164848002541930839766836371999528147246883571573578813773108520736901898161233252797410568976625868470114405566574667068643339352996187959316144899066170241429926495197002443811521093118456417779182909391630885947101798487630769153481402603727388425768431713902793354487652567879936735884086270919242973609669655735768412288726122299701992123486637874322768262656649451141411662642962410286742940631649227960940999254894427178412218392113075371126413731310023437946495328880955034101258456599926987609542380871247986081937992809964300142222802686002569765364351201696789193747516112628923755469476511021927803672707926243664663989271152433959193768288735397792243229565006105543803689203790202638057710265340701315755172408196471705277840627180884000753144372050216457505602031593068628538380241883682709072136634406199426979035048884584649836149853677500929304687152035702849594494374309042069050317467940728040135607655089961358905494004378766703666769899427890777587890624999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

And, when I try to create a finite field with it, using Fp = GF(p), where p is the above prime, it doesn't finish executing in Sage Notebook. Any ideas what the problem might be and how to overcome it?

2017-11-15 09:28:48 -0600 commented answer Lattices in Sage

Thanks for the answer. Though, I wonder whether it is the correct solution here. Please check the above modified question, with some actual values comparing the results of Magma and Sage.

2017-11-15 09:27:56 -0600 edited question Lattices in Sage

I have the following Magma code, and I want to rewrite it in Sage.

L:=Lattice(Matrix(Rationals(),2,2,[N2t,0,tau,1]), Matrix(Rationals(),2,2,[1,0,0,D]));
"Lattice:\n",L;
"\nBasis matrix:\n",LLLBasisMatrix(L);

In Sage I have something like this:

M = Matrix(QQ, [(N2t,0,tau,1), (1,0,0,D)])
M.LLL()

Whose output is not exactly the same thing produced by the above Magma code. I think the main problem is that I use a matrix and just apply the LLL algorithm to it in the Sage part. Whereas, in Magma there a lattice created, and then the LLLBasisMatrixfunction (https://magma.maths.usyd.edu.au/magma...) called. Roughly speaking that function does this:

Given a lattice L with basis matrix B, return the LLL basis matrix B' of L, together with the transformation matrix T such that B'=TB. The LLL basis matrix B' is simply defined to be a LLL-reduced form of B; it is stored in L when computed and subsequently used internally by many lattice functions. The LLL basis matrix will be created automatically internally as needed with δ=0.999 by default (note that this is different from the usual default of 0.75); by the use of parameters to this function one can ensure that the LLL basis matrix is created in a way which is different to the default.

How does one create a lattice in Sage? And does Sage have a function similar to LLLBasisMatrix above? If not, how can I achieve the same functionality in Sage?

As for numeric example, I have the following values:

N2t = 1136868377216160297393798828125
D = 53364935730486508893809772233249725927747397616650814998641
tau = 954690521650617175389887577728

and if I call the above Magma code with these values, I get the following result for the basis matrix:

[-182177855565543122003911250397                               1]
[ 772512666085074053385976327331                               2]

whereas if I call the above Sage code with the above values, I get the following result:

[1136868377216160297393798828125                                                           0                              954690521650617175389887577728                                                           1]
[1                                                           0                                                           0 53364935730486508893809772233249725927747397616650814998641]