Thanks! I will think about your suggestions.
I asked you since I know you are a cryptographer. I assume cryptographers know all about reversing hashes! Of course the question was in fact addressed to the whole list. Thanks again, Michel On Nov 12, 4:30 pm, Martin Albrecht <[EMAIL PROTECTED]> wrote: > On Wednesday 12 November 2008, Michel wrote: > > > > > Ok that hint was not sufficient. > > > What function(s) from the m4ri library would allow me to attack this > > problem? > > How do I express that the solution of the system is supposed to be > > sparse > > (which is a non-linear condition)? > > As far as I can tell there is no real reference manual for m4ri. > > > Regards, > > Michel > > > BTW I more or less know how this problem is attacked in characteristic > > zero. > > > On Nov 12, 11:10 am, Michael Brickenstein <[EMAIL PROTECTED]> wrote: > > >http://m4ri.sagemath.org/performance.html > > > > On 12 Nov., 11:07, Michel <[EMAIL PROTECTED]> wrote: > > > > > If the equations are really linear, then it's trivial. > > > > > Ah, can you tell me more? > > > > > Regards, > > > > Michel > > Hi there, > > I am surprised that this question is addressed to me and not to [sage-devel] > in general. If I understand correctly, you are not asking how to solve a > system of linear equations (this is what Michael referred to M4RI for) but > how to express the low hamming weight of the solution. > > I don't have an elegant solution. > > One way to express sparsity is to add say quadratic equations of the form x_i* > x_j = 0 for random i and j with i != j to your equation system. However, this > approach is very limited. > > Another approach: > > sage: A = random_matrix(GF(2),64,782) # 781 + constant coefficient > sage: VS = A.right_kernel() # very slow due to silly reasons > sage: M = VS.basis_matrix() #also slow due to silly reasons > > Now the problem is: Is there a linear combination of rows with hamming weight > smaller than some threshold, right? This smells like a hard problem to me. > > You might get lucky though: > > sage: mx = M.ncols() > sage: oldr = 0 > sage: for r in range(M.nrows()): > ... if sum(map(ZZ,M[r])) < mx: > ... mx = sum(map(ZZ,M[r])) > .... oldr = r > sage: mx > 18 > > Does this help? I suppose I'm only telling you things you already knew. > > PS: M4RI does have a reference manual. I think M4RI mainly lacks high-level > documentation like a tutorial and such. > > -- > name: Martin Albrecht > _pgp:http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > _www:http://www.informatik.uni-bremen.de/~malb > _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
