[sage-devel] Re: Parent structure class hierarchy

[Joseph Hundley]

Thanks for the advice and the link to the updated element class hierarchy. 

If I understand correctly, the consensus is that it's not worth my time 
fussing over which parent class to use 
and I might as well just use Parent, and it's *maybe* still worth my time 
fussing over which 
element class to use?

I remark that maybe when someone qualified has some time it would be worth 
updating Simon's 
how-to 
at 
http://doc.sagemath.org/html/en/thematic_tutorials/coercion_and_categories.html#base-classes.

This bit appears (to me, anyway) to run counter to what I'm hearing here.

Sage provides appropriate sub–classes of Parent and Element for a variety 
of more concrete algebraic structures, such as groups, rings, or fields, 
and of their elements Since we wish to implement a special kind of 
fields, namely fraction fields, it makes sense to build on top of the base 
class sage.rings.ring.Field provided by Sage.


Again, thanks for the advice.

Best, 
Joe 

On Friday, August 5, 2016 at 3:51:07 PM UTC-4, Simon King wrote:
>
> Hi Jeroen, 
>
> On 2016-08-05, Jeroen Demeyer  
> wrote: 
> > Pointers are welcome. 
>
> #18756: It makes it possible for a category to define a coerce action 
> for its objects, providing a multiplication/addition/... for the 
> elements of the objects. A coerce action can be implemented in Cython 
> and can use cythoned methods of the elements (think of _lmul_, which is 
> a cython method). Thus, it is not a problem if the parents are 
> implemented in Python, as long as the action and the element's helper 
> methods are implemented in Cython. 
>
> In this ticket, I move all the coercion functionality to Element. 
>
> Best regards, 
> Simon 
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] bug in number field ideals?

[Justin C. Walker]

On Aug 5, 2016, at 15:50 , Justin C. Walker wrote:

> 
> On Aug 5, 2016, at 11:59 , John Cremona wrote:
> 
>> Andrew Sutherland reports the following:
>> 
>> After
>> 
>> x = polygen(QQ)
>> R = QQ[x]
>> pol = R([-1,-3,6,4,-5,-1,1])
>> K = NumberField(pol,'a')
>> I = K.ideal([1,1])
>> 
>> all is well, but then
>> 
>> I
>> 
>> (to display the unit ideal) takes a long, and variable, time.  What is
>> going on?  (Don't bother telling me that it is silly to repeat the
>> ideal generator, we extracted this from more complicated code while
>> debugging.)
> 
> FWIW, it happened between 6.10 (the latests one I can build in 10.6.8) and 
> 7.0 (the first I built on 10.11).  Unless there's a really subtle difference 
> between the two versions of OS X.

I spoke to soon.  I tried this on a 6.10 version that had been up and running 
for some time (192 days; not continuously in use - I use it for random 
intermittent calculations...).

I started a fresh copy on the same system and got the same noticeably long time 
to just display "I".

Sorry for the noise.

--
Justin C. Walker, Curmudgeon-At-Large, Director
Institute for the Enhancement of the Director's Income

The path of least resistance:
it's not just for electricity any more.




-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] bug in number field ideals?

[Justin C. Walker]

On Aug 5, 2016, at 11:59 , John Cremona wrote:

> Andrew Sutherland reports the following:
> 
> After
> 
> x = polygen(QQ)
> R = QQ[x]
> pol = R([-1,-3,6,4,-5,-1,1])
> K = NumberField(pol,'a')
> I = K.ideal([1,1])
> 
> all is well, but then
> 
> I
> 
> (to display the unit ideal) takes a long, and variable, time.  What is
> going on?  (Don't bother telling me that it is silly to repeat the
> ideal generator, we extracted this from more complicated code while
> debugging.)

FWIW, it happened between 6.10 (the latests one I can build in 10.6.8) and 7.0 
(the first I built on 10.11).  Unless there's a really subtle difference 
between the two versions of OS X.

HTH

--
Justin C. Walker, Curmudgeon at Large
Director
Institute for the Enhancement of the Director's income
---
Question 43:
What if the hokey pokey
really *is* what it’s all about?
--

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Parent structure class hierarchy

[Simon King]

Hi Jeroen,

On 2016-08-05, Jeroen Demeyer  wrote:
> Pointers are welcome.

#18756: It makes it possible for a category to define a coerce action
for its objects, providing a multiplication/addition/... for the
elements of the objects. A coerce action can be implemented in Cython
and can use cythoned methods of the elements (think of _lmul_, which is
a cython method). Thus, it is not a problem if the parents are
implemented in Python, as long as the action and the element's helper
methods are implemented in Cython.

In this ticket, I move all the coercion functionality to Element.

Best regards,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Parent structure class hierarchy

[Jeroen Demeyer]

On 2016-08-05 21:15, Simon King wrote:

By the way, concerning element classes, if I recall correctly from your
previous posts, you are working on unification of the Element class
hierarchy


Yes. See #20767


I also have a
couple of tickets dedicated to that (for example, making it easier to
implement algebraic structures using actions). Shall I give you a
pointer, or do you take them into account already?


Pointers are welcome.

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Changes to the coercion model / Element classes

[Jeroen Demeyer]

Hello all,

In ticket #20767, I have made two important changes to the coercion 
model for arithmetic:


1. Move all coercion logic from RingElement, ModuleElement and the like 
to Element.


2. Change the implementation of double-underscore methods like __add__ 
to return NotImplemented if one argument is not a Sage Element and 
coercion fails.


More details at the ticket: https://trac.sagemath.org/ticket/20767

For everyone who has been struggling with arithmetic using the coercion 
model, it might be worth having a look at that ticket and see if it 
fixes the problem. And obviously, I welcome reviewers :-)


Jeroen.

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Parent structure class hierarchy

[Simon King]

Hi Jeroen,

On 2016-08-05, Jeroen Demeyer  wrote:
> There are parent classes like Ring, Field, ... They are defined in 
> various files, for example in src/sage/rings/ring.pyx
>
> However, it is not really clear how they should be used, especially 
> because there is a lot of overlap with categories.

I think in the case of parent classes it is fair to say that they are
already superseded by categories.

By the way, concerning element classes, if I recall correctly from your
previous posts, you are working on unification of the Element class
hierarchy --- which I do believe is a good idea, and I also have a
couple of tickets dedicated to that (for example, making it easier to
implement algebraic structures using actions). Shall I give you a
pointer, or do you take them into account already?

In a way, I should modify what I recommended in a previous post: While
believe that arithmetics should rely on the cythonized framework currently
provided by, say, RingElement, that framework would better be moved to
Element.
So, for the time being, it makes sense to start with RingElement or
ModuleElement depending on the application, but in the long run Element
should just be fine.

Best regards,
Simon


-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: bug in number field ideals?

[John Cremona]

On 5 August 2016 at 19:59, John Cremona  wrote:
> Andrew Sutherland reports the following:
>
> After
>
> x = polygen(QQ)
> R = QQ[x]
> pol = R([-1,-3,6,4,-5,-1,1])
> K = NumberField(pol,'a')
> I = K.ideal([1,1])
>
> all is well, but then
>
> I
>
> (to display the unit ideal) takes a long, and variable, time.  What is
> going on?  (Don't bother telling me that it is silly to repeat the
> ideal generator, we extracted this from more complicated code while
> debugging.)

More information:  this apparently only happens the first time a
number field is created:

"If you press ctrl-c you will see it is stuck inside pari's bnfinit
(which is why I did not initially report it to Sage). If you then
execute the command again it will work fine (or more generally, if you
do just about anything else with pari number fields before executing
the problematic line it will work fine.

I cannot reproduce the problem in pari, which is why I have not
reported it to them either. There is something very weird going on
that appears to only happen the first time Sage calls bnfinit, and it
is specific to this field. This is why we rarely see the problem on
www.lmfdb.org, but occasionally do."

>
> John

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Parent structure class hierarchy

[Simon King]

Hi Travis,

On 2016-08-05, Travis Scrimshaw  wrote:
> On Friday, August 5, 2016 at 10:11:13 AM UTC-5, Andrew wrote:
> It is not true that CFM is implemented in Python. The addition and scalar 
> coefficient action are done in cython in dict_addition. See 
> https://trac.sagemath.org/ticket/20680, and Nicolas and I also looked into 
> Cythonizing CFM elements (I have a branch with some progress on this).

As I said, I am a bit biased, and maybe I got a wrong impression from
the fact that sage.combinat.free_module is a python module.

> There are also likely improvements to be made to the current framework for 
> the algebras (i.e., the *_on_basis methods), but it makes a very simple way 
> to do implementations

True. But when I last looked at CFM (some time ago), it wasn't easy to
get a good performance, and I am glad that you and Nicolas are working
on cythonization.

> and removes a lot of redundancy.

Or *introduces* redundancy, since people may feel tempted to reimplement
stuff (without doubt in a cleaner way) that already is available.

One example that I recently met is not about CFM, but may illustrate what
I mean: There is a fast nasty boilerplate implementation of binary trees
at sage.misc.binary_tree, and IN ADDITION to that a hight level
implementation at sage.combinat.binary_tree written in Python and relying
on ClonableIntArray, which is fast but likely isn't a data structure
specially dedicated to binary trees.

Why should one rewrite everything ("reinvent the wheel") on top of
non-specific data structures rather than using the existing boilerplate
implementation as a backend of nicer code ("build the car")?

Cheers,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] bug in number field ideals?

[John Cremona]

Andrew Sutherland reports the following:

After

x = polygen(QQ)
R = QQ[x]
pol = R([-1,-3,6,4,-5,-1,1])
K = NumberField(pol,'a')
I = K.ideal([1,1])

all is well, but then

I

(to display the unit ideal) takes a long, and variable, time.  What is
going on?  (Don't bother telling me that it is silly to repeat the
ideal generator, we extracted this from more complicated code while
debugging.)

John

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Parent structure class hierarchy

[Travis Scrimshaw]

On Friday, August 5, 2016 at 10:11:13 AM UTC-5, Andrew wrote:
>
>
>
> On Friday, 5 August 2016 18:23:03 UTC+10, Simon King wrote:
>
>> So, my advice is: 
>> - Start with one of the element base classes and implement arithmetics 
>>   there (and be careful to comply with Sage's coercion model). 
>> - Use the category framework to determine whether a parent it is a (say) 
>>   ring or a module. 
>> - CombinatorialFreeModule is convenient, but any time critical stuff 
>>   should be implemented on the level of its elements. 
>>
>
> Hi Simon,
>
> Would you mind expanding a little on this? I have some modules, for the 
> symmetric groups for example, that are implemented using  
> CombinatorialFreeModule, together with the realization code as there are 
> several interesting bases. It's reasonably fast in "small" examples but I'd 
> be happy if there was a way to make it faster. The indexing set for the 
> basis has a lot of combinatorial data attached to it that described 
> important properties of the module -- for example, it is graded and the 
> indexing set gives the grading -- so I need the indexing set. The algebra 
> action is defined by certain linear maps on the basis elements.. In 
> different incarnations these modules are defined over Z, or any ring, or 
> QQ[x]. How would you recommend implementing this?
>
> It is not true that CFM is implemented in Python. The addition and scalar 
coefficient action are done in cython in dict_addition. See 
https://trac.sagemath.org/ticket/20680, and Nicolas and I also looked into 
Cythonizing CFM elements (I have a branch with some progress on this). 
There are also likely improvements to be made to the current framework for 
the algebras (i.e., the *_on_basis methods), but it makes a very simple way 
to do implementations and removes a lot of redundancy. Though some of the 
design choice is based on how significant the overhead is compared to other 
operations (to which, with a bit more work, one can pull out bottlenecks 
into Cython).

Best,
Travis


 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Parent structure class hierarchy

[Andrew]

On Friday, 5 August 2016 18:23:03 UTC+10, Simon King wrote:

> So, my advice is: 
> - Start with one of the element base classes and implement arithmetics 
>   there (and be careful to comply with Sage's coercion model). 
> - Use the category framework to determine whether a parent it is a (say) 
>   ring or a module. 
> - CombinatorialFreeModule is convenient, but any time critical stuff 
>   should be implemented on the level of its elements. 
>

Hi Simon,

Would you mind expanding a little on this? I have some modules, for the 
symmetric groups for example, that are implemented using  
CombinatorialFreeModule, together with the realization code as there are 
several interesting bases. It's reasonably fast in "small" examples but I'd 
be happy if there was a way to make it faster. The indexing set for the 
basis has a lot of combinatorial data attached to it that described 
important properties of the module -- for example, it is graded and the 
indexing set gives the grading -- so I need the indexing set. The algebra 
action is defined by certain linear maps on the basis elements.. In 
different incarnations these modules are defined over Z, or any ring, or 
QQ[x]. How would you recommend implementing this?

Andrew

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] fplll 5.0 in sage

[Johan S . H . Rosenkilde]

Sounds pretty great!

> [X] Yes
> [ ] No
> [ ] Maybe

Best,
Johan

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] fplll 5.0 in sage

[Thierry]

Hi,

giving interfaces initially developped for Sage to upstream is the way to go.
The benefits of free-software ecosystem should be two-ways, otherwise Sage is
only predating other softwares.

Moreover with such an approach, upstream will make it cover all features when
they appear so that they are automatically exposed to Sage users, and they can
ship Python bindings independently of Sage (which many mathematician consider
as too big for their specific needs). In the concrete case of fpLLL, we already
had the case where some developper reimplemented a feature of fpLLL just
because it was not exposed by our partial (not up-to-date) interface, see
https://trac.sagemath.org/ticket/15758 

A common Python bindings is probably a better place to cut (for modularity)
than between upstream binary and Sage Cython bindings (though i admint that in
some specific cases, it may add a slowing Python layer).

+1 for using fpylll and make it standard.

Ciao,
Thierry



On Fri, Aug 05, 2016 at 12:32:53PM +0100, 'Martin R. Albrecht' via sage-devel 
wrote:
> Hi Sage developers,
> 
> *tl;dr* Fplll 5.0 is about to hit the streets. It’s a major improvement
>  over Fplll 4.* which we currently ship with Sage. To update we need to
>  change the user interface of the function `IntegerMatrix.BKZ`. I
>  suggest to drop Sage’s own interface to Fplll in favour of the official
>  Fpylll interface, which I propose to make a standard package.
> 
> [ ] Yes
> [ ] No
> [ ] Maybe
> 
> # Details #
> 
> We are getting ready to release Fplll 5.0.0. Here are some highlights
> from the changelog https://raw.githubusercontent.com/fplll/fplll/master/NEWS
> 
> - fplll switched to more open development model on GitHub
>   with a bigger development community
> 
> - public implementation of all techniques collectively known as BKZ 2.0.
>   BKZ in block size 80 is a reasonably easy computation now.
> 
> - build system overhaul, automated tests, test coverage increase
> 
> - Self-Dual BKZ and Slide reduction
> 
> - faster, recursive enumeration implementation
> 
> - Gaussian lattice sieving
> 
> - optional support for doubledouble and quaddouble
> 
>   https://github.com/fplll/fplll
> 
> If you care only about LLL then this release won’t change much for you,
> because Sage doesn’t ship libqd. But if you care about stronger lattice
> reduction this release makes a huge difference.
> 
> # Sage Interface #
> 
> (a) Sage’s public interface is through the functions `IntegerMatrix.LLL` and
> `IntegerMatrix.BKZ` and a few functions on the integer lattice class.
> 
> (b) These call some in `libs.fplll`
> 
> The the interface for calling BKZ has changed and does not match Sage’s
> interface (a). We could write a translation layer, but I’d prefer to
> simply change it. Users will want to use the new interface.
> 
> I also suggest to replace (b) completely with 
> 
>   https://github.com/fplll/fpylll
> 
> It’s a Cython interface to fplll + additional Python code which started
> as a fork of Sage’s Cython interface. It’s much more flexible and
> powerful than what Sage has to offer. For example, it (easily) allows to
> implement BKZ and LLL variants in pure Python. Strong lattice reduction
> is a major area of research for cryptographers at the moment and this
> library aims to make experimentation for this easy.
> 
> It is mainly written and maintained by me. Lattice-based cryptography
> will be research area for the foreseeable future and this code is a key
> component of this research for me, so I plan to maintain and improve it
> over the next few years. I do commit to maintaining it in Sage, too.
> 
> The code has tests which are run on every check in.
> 
> Yes, No, Maybe?
> 
> Cheers,
> Martin
> 
> PS: Here is some random benchmark:
> 
> $ ./latticegen q 100 50 30 b > ~/test_lattice.txt
> 
> new fplll
> 
> $ time ./fplll -a bkz -s ../strategies/default.json -bkzautoabort -v -b 60 
> ~/test_lattice.txt > /dev/null
> Entering BKZ:
> block size:  60, flags: 0x0021, max_loops:   0, max_time: 0.0, autoAbort: 
> (1.,  5), 
> 
> End of BKZ loop0, time =12.832s, r_0 = 1.80e10, slope = -0.056809, 
> log2(nodes) = 28.142067
> End of BKZ loop1, time =25.072s, r_0 = 1.07e10, slope = -0.050003, 
> log2(nodes) = 29.120454
> End of BKZ loop2, time =36.836s, r_0 = 1.00e10, slope = -0.048468, 
> log2(nodes) = 29.623702
> End of BKZ loop3, time =48.944s, r_0 = 9.42e9, slope = -0.048443, 
> log2(nodes) = 29.991966
> End of BKZ loop4, time =58.176s, r_0 = 9.42e9, slope = -0.048230, 
> log2(nodes) = 30.207781
> End of BKZ loop5, time =67.904s, r_0 = 9.42e9, slope = -0.048134, 
> log2(nodes) = 30.414377
> End of BKZ loop6, time =78.040s, r_0 = 9.42e9, slope = -0.048500, 
> log2(nodes) = 30.611421
> End of BKZ loop7, time =87.780s, r_0 = 9.42e9, slope = -0.048197, 
> log2(nodes) = 30.784449
> End of BKZ loop8, time =96.468s, r_0 = 9.42e9, slope = -0.047948, 
> log2(nodes) = 30.910345
> End of BKZ loop

[sage-devel] Re: fplll 5.0 in sage

[Dima Pasechnik]

On Friday, August 5, 2016 at 12:32:58 PM UTC+1, Martin Albrecht wrote:
>
> Hi Sage developers, 
>
> *tl;dr* Fplll 5.0 is about to hit the streets. It’s a major improvement 
>  over Fplll 4.* which we currently ship with Sage. To update we need to 
>  change the user interface of the function `IntegerMatrix.BKZ`. I 
>  suggest to drop Sage’s own interface to Fplll in favour of the official 
>  Fpylll interface, which I propose to make a standard package. 
>
> [X ] Yes 
> [ ] No 
> [ ] Maybe 
>
> # Details # 
>
> We are getting ready to release Fplll 5.0.0. Here are some highlights 
> from the changelog 
> https://raw.githubusercontent.com/fplll/fplll/master/NEWS 
>
> - fplll switched to more open development model on GitHub 
>   with a bigger development community 
>
> - public implementation of all techniques collectively known as BKZ 2.0. 
>   BKZ in block size 80 is a reasonably easy computation now. 
>
> - build system overhaul, automated tests, test coverage increase 
>
> - Self-Dual BKZ and Slide reduction 
>
> - faster, recursive enumeration implementation 
>
> - Gaussian lattice sieving 
>
> - optional support for doubledouble and quaddouble 
>
>   https://github.com/fplll/fplll 
>
> If you care only about LLL then this release won’t change much for you, 
> because Sage doesn’t ship libqd. But if you care about stronger lattice 
> reduction this release makes a huge difference. 
>
> # Sage Interface # 
>
> (a) Sage’s public interface is through the functions `IntegerMatrix.LLL` 
> and 
> `IntegerMatrix.BKZ` and a few functions on the integer lattice class. 
>
> (b) These call some in `libs.fplll` 
>
> The the interface for calling BKZ has changed and does not match Sage’s 
> interface (a). We could write a translation layer, but I’d prefer to 
> simply change it. Users will want to use the new interface. 
>
> I also suggest to replace (b) completely with 
>
>   https://github.com/fplll/fpylll 
>
> It’s a Cython interface to fplll + additional Python code which started 
> as a fork of Sage’s Cython interface. It’s much more flexible and 
> powerful than what Sage has to offer. For example, it (easily) allows to 
> implement BKZ and LLL variants in pure Python. Strong lattice reduction 
> is a major area of research for cryptographers at the moment and this 
> library aims to make experimentation for this easy. 
>
> It is mainly written and maintained by me. Lattice-based cryptography 
> will be research area for the foreseeable future and this code is a key 
> component of this research for me, so I plan to maintain and improve it 
> over the next few years. I do commit to maintaining it in Sage, too. 
>
> The code has tests which are run on every check in. 
>
> Yes, No, Maybe? 
>
> Cheers, 
> Martin 
>
> PS: Here is some random benchmark: 
>
> $ ./latticegen q 100 50 30 b > ~/test_lattice.txt 
>
> new fplll 
>
> $ time ./fplll -a bkz -s ../strategies/default.json -bkzautoabort -v -b 60 
> ~/test_lattice.txt > /dev/null 
> Entering BKZ: 
> block size:  60, flags: 0x0021, max_loops:   0, max_time: 0.0, autoAbort: 
> (1.,  5), 
>
> End of BKZ loop0, time =12.832s, r_0 = 1.80e10, slope = -0.056809, 
> log2(nodes) = 28.142067 
> End of BKZ loop1, time =25.072s, r_0 = 1.07e10, slope = -0.050003, 
> log2(nodes) = 29.120454 
> End of BKZ loop2, time =36.836s, r_0 = 1.00e10, slope = -0.048468, 
> log2(nodes) = 29.623702 
> End of BKZ loop3, time =48.944s, r_0 = 9.42e9, slope = -0.048443, 
> log2(nodes) = 29.991966 
> End of BKZ loop4, time =58.176s, r_0 = 9.42e9, slope = -0.048230, 
> log2(nodes) = 30.207781 
> End of BKZ loop5, time =67.904s, r_0 = 9.42e9, slope = -0.048134, 
> log2(nodes) = 30.414377 
> End of BKZ loop6, time =78.040s, r_0 = 9.42e9, slope = -0.048500, 
> log2(nodes) = 30.611421 
> End of BKZ loop7, time =87.780s, r_0 = 9.42e9, slope = -0.048197, 
> log2(nodes) = 30.784449 
> End of BKZ loop8, time =96.468s, r_0 = 9.42e9, slope = -0.047948, 
> log2(nodes) = 30.910345 
> End of BKZ loop9, time =   117.404s, r_0 = 9.42e9, slope = -0.048360, 
> log2(nodes) = 31.053923 
> End of BKZ loop   10, time =   143.812s, r_0 = 9.42e9, slope = -0.048163, 
> log2(nodes) = 31.180644 
> End of BKZ loop   11, time =   164.652s, r_0 = 9.42e9, slope = -0.047898, 
> log2(nodes) = 31.286769 
> End of BKZ loop   12, time =   203.492s, r_0 = 9.20e9, slope = -0.048275, 
> log2(nodes) = 31.392854 
> End of BKZ loop   13, time =   236.376s, r_0 = 9.20e9, slope = -0.047879, 
> log2(nodes) = 31.501613 
> End of BKZ loop   14, time =   284.636s, r_0 = 9.20e9, slope = -0.048120, 
> log2(nodes) = 31.608491 
> End of BKZ loop   15, time =   310.472s, r_0 = 9.20e9, slope = -0.047999, 
> log2(nodes) = 31.696863 
> End of BKZ loop   16, time =   328.624s, r_0 = 9.20e9, slope = -0.048367, 
> log2(nodes) = 31.795334 
> End of BKZ loop   17, time =   340.940s, r_0 = 9.20e9, slope = -0.048103, 
> log2(nodes) = 31.876720 
> End of BKZ loop   18, 

[sage-devel] fplll 5.0 in sage

['Martin R. Albrecht' via sage-devel]

Hi Sage developers,

*tl;dr* Fplll 5.0 is about to hit the streets. It’s a major improvement
 over Fplll 4.* which we currently ship with Sage. To update we need to
 change the user interface of the function `IntegerMatrix.BKZ`. I
 suggest to drop Sage’s own interface to Fplll in favour of the official
 Fpylll interface, which I propose to make a standard package.

[ ] Yes
[ ] No
[ ] Maybe

# Details #

We are getting ready to release Fplll 5.0.0. Here are some highlights
from the changelog https://raw.githubusercontent.com/fplll/fplll/master/NEWS

- fplll switched to more open development model on GitHub
  with a bigger development community

- public implementation of all techniques collectively known as BKZ 2.0.
  BKZ in block size 80 is a reasonably easy computation now.

- build system overhaul, automated tests, test coverage increase

- Self-Dual BKZ and Slide reduction

- faster, recursive enumeration implementation

- Gaussian lattice sieving

- optional support for doubledouble and quaddouble

  https://github.com/fplll/fplll

If you care only about LLL then this release won’t change much for you,
because Sage doesn’t ship libqd. But if you care about stronger lattice
reduction this release makes a huge difference.

# Sage Interface #

(a) Sage’s public interface is through the functions `IntegerMatrix.LLL` and
`IntegerMatrix.BKZ` and a few functions on the integer lattice class.

(b) These call some in `libs.fplll`

The the interface for calling BKZ has changed and does not match Sage’s
interface (a). We could write a translation layer, but I’d prefer to
simply change it. Users will want to use the new interface.

I also suggest to replace (b) completely with 

  https://github.com/fplll/fpylll

It’s a Cython interface to fplll + additional Python code which started
as a fork of Sage’s Cython interface. It’s much more flexible and
powerful than what Sage has to offer. For example, it (easily) allows to
implement BKZ and LLL variants in pure Python. Strong lattice reduction
is a major area of research for cryptographers at the moment and this
library aims to make experimentation for this easy.

It is mainly written and maintained by me. Lattice-based cryptography
will be research area for the foreseeable future and this code is a key
component of this research for me, so I plan to maintain and improve it
over the next few years. I do commit to maintaining it in Sage, too.

The code has tests which are run on every check in.

Yes, No, Maybe?

Cheers,
Martin

PS: Here is some random benchmark:

$ ./latticegen q 100 50 30 b > ~/test_lattice.txt

new fplll

$ time ./fplll -a bkz -s ../strategies/default.json -bkzautoabort -v -b 60 
~/test_lattice.txt > /dev/null
Entering BKZ:
block size:  60, flags: 0x0021, max_loops:   0, max_time: 0.0, autoAbort: 
(1.,  5), 

End of BKZ loop0, time =12.832s, r_0 = 1.80e10, slope = -0.056809, 
log2(nodes) = 28.142067
End of BKZ loop1, time =25.072s, r_0 = 1.07e10, slope = -0.050003, 
log2(nodes) = 29.120454
End of BKZ loop2, time =36.836s, r_0 = 1.00e10, slope = -0.048468, 
log2(nodes) = 29.623702
End of BKZ loop3, time =48.944s, r_0 = 9.42e9, slope = -0.048443, 
log2(nodes) = 29.991966
End of BKZ loop4, time =58.176s, r_0 = 9.42e9, slope = -0.048230, 
log2(nodes) = 30.207781
End of BKZ loop5, time =67.904s, r_0 = 9.42e9, slope = -0.048134, 
log2(nodes) = 30.414377
End of BKZ loop6, time =78.040s, r_0 = 9.42e9, slope = -0.048500, 
log2(nodes) = 30.611421
End of BKZ loop7, time =87.780s, r_0 = 9.42e9, slope = -0.048197, 
log2(nodes) = 30.784449
End of BKZ loop8, time =96.468s, r_0 = 9.42e9, slope = -0.047948, 
log2(nodes) = 30.910345
End of BKZ loop9, time =   117.404s, r_0 = 9.42e9, slope = -0.048360, 
log2(nodes) = 31.053923
End of BKZ loop   10, time =   143.812s, r_0 = 9.42e9, slope = -0.048163, 
log2(nodes) = 31.180644
End of BKZ loop   11, time =   164.652s, r_0 = 9.42e9, slope = -0.047898, 
log2(nodes) = 31.286769
End of BKZ loop   12, time =   203.492s, r_0 = 9.20e9, slope = -0.048275, 
log2(nodes) = 31.392854
End of BKZ loop   13, time =   236.376s, r_0 = 9.20e9, slope = -0.047879, 
log2(nodes) = 31.501613
End of BKZ loop   14, time =   284.636s, r_0 = 9.20e9, slope = -0.048120, 
log2(nodes) = 31.608491
End of BKZ loop   15, time =   310.472s, r_0 = 9.20e9, slope = -0.047999, 
log2(nodes) = 31.696863
End of BKZ loop   16, time =   328.624s, r_0 = 9.20e9, slope = -0.048367, 
log2(nodes) = 31.795334
End of BKZ loop   17, time =   340.940s, r_0 = 9.20e9, slope = -0.048103, 
log2(nodes) = 31.876720
End of BKZ loop   18, time =   350.668s, r_0 = 9.20e9, slope = -0.048362, 
log2(nodes) = 31.940467
End of BKZ: success

fplll 4.* in Sage:

$ time fplll -a bkz -bkzautoabort -v -b 60 -bkzmaxloops 1
~/test_lattice.txt

-> killed after 80 minutes without finishing the first tour.

-- 

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: 

Re: [sage-devel] Re: Parent structure class hierarchy

[Jeroen Demeyer]

On 2016-08-05 10:22, Simon King wrote:

I believe there should *not* be a hierarchy of parent base classes
similar to the element classes.


I believe that there should *not* be such a hierarchy of Element classes 
either. Ticket #20767 already removes many of the differences between 
those Element classes.


--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Parent structure class hierarchy

[Jeroen Demeyer]

On 2016-08-05 01:57, Joseph Hundley wrote:

Is there some analogue of
http://combinat.sagemath.org/doc/reference/structure/sage/structure/element.html#
for parent structures?


There are parent classes like Ring, Field, ... They are defined in 
various files, for example in src/sage/rings/ring.pyx


However, it is not really clear how they should be used, especially 
because there is a lot of overlap with categories.


--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Parent structure class hierarchy

[Simon King]

Hi Joseph,

On 2016-08-05, Travis Scrimshaw  wrote:
> Hey Joseph,
>It is basically just Parent. I don't know of any other ABC that is a 
> subclass of Parent. Although a common concrete implementation of Parent 
> that is often used as a base class (for algebras) is 
> CombinatorialFreeModule.

I believe there should *not* be a hierarchy of parent base classes
similar to the element classes. After all, the (cythonised!) element
classes exist in order to have fast arithmetic methods. These methods
apply to the elements, not to the parents.

Do you think that there are methods for parents that are specific to
(say) rings and absolutely need to be fast?

I might be a bit biased and maybe got a wrong impression. Anyway:
Using CombinatorialFreeModule seems like a bad idea to me if you want
to have a fast arithmetic. After all, it is pure Python code, and
moreover all these ..._on_basis methods seem to be called in a
very convoluted way, meaning that there is a high calling overhead in
each single arithmetic operation.

So, my advice is:
- Start with one of the element base classes and implement arithmetics
  there (and be careful to comply with Sage's coercion model).
- Use the category framework to determine whether a parent it is a (say)
  ring or a module.
- CombinatorialFreeModule is convenient, but any time critical stuff
  should be implemented on the level of its elements.

Best regards,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: So...who are the Singular experts?

[leif]

leif wrote:
> Erik Bray wrote:
>> On Thu, Aug 4, 2016 at 3:28 PM, leif  wrote:
>>> Erik Bray wrote:
 On Thu, Aug 4, 2016 at 11:26 AM, leif  wrote:
> We removed any explicit mention of MPIR ('-lmpir', '#include ')
> a while ago, but a few newer packages may indeed recognize MPIR
> meanwhile and link to that instead.  But I'm not aware of a single one.

 Well, what happens with --enable-gmpcompat, at least on Windows, is
 that two separate libraries are built: gmp and mpir.  I guess the
 former is as close to possible as plain gmp, without any features
 added by mpir (in fact the gmp library is a little bit smaller).  The
 MPIR and GMP DLLs have no dependencies on each other.
>>>
>>> libgmp is identical to libmpir (likewise, gmp.h to mpir.h),
>>> '--enable-gmpcompat' just creates copies under a different name.
>>>
>>> (The shared libraries also carry the same version.)
>>
>> You're right. I see now that they are identical.  The only difference
>> I saw was specific to Windows, and was actually only in the size of
>> the import libs, not the DLLs themselves.  The size difference in the
>> import libs is accounted for in the fact that the import lib mentions
>> the DLL filename in several places.
>>
>> So if --enable-cmpcompat is literally just making copies maybe we
>> should remove that, and replace the copies with a rename, or a
>> symlink.
>>
>>> No idea what's going on on Cygwin, but certainly MPIR's libgmp is not
>>> "more compatible" to GMP's than libmpir is.
>>
>> See above--there's no significant difference.
>>
>>> At some point these were actually the same files, not sym- but
>>> hardlinked, but neither is supported on Cygwin and I guess that's why we
>>> nowadays have two real copies, which isn't necessary either.  (If
>>> '--enable-gmpcompat' is used, in Sage at least *only* gmp.h and
>>> libgmp[xx] should get installed, to avoid exactly what happened below.
>>> If the linker bails out because it cannot find -lmpir, fine, since you
>>> know there's a mistake in specifying libraries.  Similar for includes
>>> and the preprocessor.)
>>>
>>>
 I did a fresh build of Singular using the current unmodified spkg and
 found that the Singular executable itself was linked with:

 -lflint -lmpfr -lmpir -lm -lsingfac -lsingcf -lflint -lmpfr -lntl
 -lgmp -lreadline -lpthread -lrt -lm -lomalloc
>>>
>>> Ouch.
>>>
>>>
 The repetitious stuff is annoying, but harmless.  The harm here is
 that there is both -lmpir and -lgmp.
>>>
>>> Well, not exactly.  If -lgmp -lmpir -lm (or -lmpir -lgmp -lm) came last,
>>> there wouldn't be a problem, since all symbols would get resolved from
>>> the same library.
>>
>> Well sure.  I haven't been able to trace exactly why a handful of
>> symbols are resolved to -lgmp first, and cleaning that mess up might
>> clarify matters.  On Linux though it doesn't seem to be a
>> problem--everything is found through -lmpir.
>>
 The -lmpir in this case comes
 from Singular's configure.in where it's added to a variable called
 FLINT_LIBS which is included in the linker flags for Singular and
 libsingular.  I don't know if there's some reason it absolutely must
 link with mpir for flint to work, but I doubt it?
>>>
>>> There was a time when this was indeed the case (FLINT requiring MPIR),
>>> and Singular using FLINT is relatively new, so presumably someone felt
>>> it was clever to explicitly use -lmpir there (too), which is of course
>>
>> I added a patch to remove this and it seems to have fixed everything.
>> I'll create a ticket with the patch.  Thanks for reading!
> 
> This apparently is specific to (Singular on) Cygwin, as otherwise my
> builds from scratch with --with-mp=gmp would have failed with a linker
> error (-lmpir: not found).  I also have no traces of mpir in the
> Singular package's build log.
> 
> CC me when you open a ticket; I'll presumably open one for changing what
> the MPIR package installs (with --enable-gmpcompat, which is of course
> the default in Sage).

I've opened #21174 [1] for the latter.


-leif

[1] https://trac.sagemath.org/ticket/21174


-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: So...who are the Singular experts?

[leif]

Erik Bray wrote:
> On Thu, Aug 4, 2016 at 3:28 PM, leif  wrote:
>> Erik Bray wrote:
>>> On Thu, Aug 4, 2016 at 11:26 AM, leif  wrote:
 We removed any explicit mention of MPIR ('-lmpir', '#include ')
 a while ago, but a few newer packages may indeed recognize MPIR
 meanwhile and link to that instead.  But I'm not aware of a single one.
>>>
>>> Well, what happens with --enable-gmpcompat, at least on Windows, is
>>> that two separate libraries are built: gmp and mpir.  I guess the
>>> former is as close to possible as plain gmp, without any features
>>> added by mpir (in fact the gmp library is a little bit smaller).  The
>>> MPIR and GMP DLLs have no dependencies on each other.
>>
>> libgmp is identical to libmpir (likewise, gmp.h to mpir.h),
>> '--enable-gmpcompat' just creates copies under a different name.
>>
>> (The shared libraries also carry the same version.)
> 
> You're right. I see now that they are identical.  The only difference
> I saw was specific to Windows, and was actually only in the size of
> the import libs, not the DLLs themselves.  The size difference in the
> import libs is accounted for in the fact that the import lib mentions
> the DLL filename in several places.
> 
> So if --enable-cmpcompat is literally just making copies maybe we
> should remove that, and replace the copies with a rename, or a
> symlink.
> 
>> No idea what's going on on Cygwin, but certainly MPIR's libgmp is not
>> "more compatible" to GMP's than libmpir is.
> 
> See above--there's no significant difference.
> 
>> At some point these were actually the same files, not sym- but
>> hardlinked, but neither is supported on Cygwin and I guess that's why we
>> nowadays have two real copies, which isn't necessary either.  (If
>> '--enable-gmpcompat' is used, in Sage at least *only* gmp.h and
>> libgmp[xx] should get installed, to avoid exactly what happened below.
>> If the linker bails out because it cannot find -lmpir, fine, since you
>> know there's a mistake in specifying libraries.  Similar for includes
>> and the preprocessor.)
>>
>>
>>> I did a fresh build of Singular using the current unmodified spkg and
>>> found that the Singular executable itself was linked with:
>>>
>>> -lflint -lmpfr -lmpir -lm -lsingfac -lsingcf -lflint -lmpfr -lntl
>>> -lgmp -lreadline -lpthread -lrt -lm -lomalloc
>>
>> Ouch.
>>
>>
>>> The repetitious stuff is annoying, but harmless.  The harm here is
>>> that there is both -lmpir and -lgmp.
>>
>> Well, not exactly.  If -lgmp -lmpir -lm (or -lmpir -lgmp -lm) came last,
>> there wouldn't be a problem, since all symbols would get resolved from
>> the same library.
> 
> Well sure.  I haven't been able to trace exactly why a handful of
> symbols are resolved to -lgmp first, and cleaning that mess up might
> clarify matters.  On Linux though it doesn't seem to be a
> problem--everything is found through -lmpir.
> 
>>> The -lmpir in this case comes
>>> from Singular's configure.in where it's added to a variable called
>>> FLINT_LIBS which is included in the linker flags for Singular and
>>> libsingular.  I don't know if there's some reason it absolutely must
>>> link with mpir for flint to work, but I doubt it?
>>
>> There was a time when this was indeed the case (FLINT requiring MPIR),
>> and Singular using FLINT is relatively new, so presumably someone felt
>> it was clever to explicitly use -lmpir there (too), which is of course
> 
> I added a patch to remove this and it seems to have fixed everything.
> I'll create a ticket with the patch.  Thanks for reading!

This apparently is specific to (Singular on) Cygwin, as otherwise my
builds from scratch with --with-mp=gmp would have failed with a linker
error (-lmpir: not found).  I also have no traces of mpir in the
Singular package's build log.

CC me when you open a ticket; I'll presumably open one for changing what
the MPIR package installs (with --enable-gmpcompat, which is of course
the default in Sage).


-leif


-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.