• Post Reply Bookmark Topic Watch Topic
  • New Topic

Polynomial Algorithms  RSS feed

 
H Melua
Ranch Hand
Posts: 172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi

I'm stock with polynoms! Assuming that I have this polynom in hex 0xA
and I want the remainder of dividing it by 0xB then how would I present this in java?

I tried doing it this way, but thats not really working!
As doing normal division, The max power of the polynom (can but) will never be greater than 0x10
What changes do i need to make to get the reminder?
Thanks
HannaH
[ November 12, 2007: Message edited by: H Melua ]
 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Given that no-one else has replied, I suspect they all thought "WTF?", like I did.

I think you're assuming that these "polynomial algorithms" are something well-known. But it doesn't look like anything I've ever seen and I did a fair amount of numerical computing.

Please give some more background, then maybe we can help.

(Yes, I do know what a "polynomial" is, but that doesn't seem to help much in understanding your code.)
 
Nicholas Jordan
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[original poster:]I want the remainder of dividing

Perhaps try modulo operator - why otherwise ?
 
H Melua
Ranch Hand
Posts: 172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Peter
Thanks for replying...

you see its not something people are likely to do in their daylife!! its all about cryptography, and in my BSc studies we didnt have to do any of it! And many people stop their academic studies at that stage... so i wasnt really thinking its well known (since even my friend Google didnt know! ), but i hoped some1 from the croud might know

Nick
Thanks to you too for replying...
But i dont know how to divide binaries (over Finite fields) to begin with
 
H Melua
Ranch Hand
Posts: 172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In all cases, i've solved this issue using "over naive" method (i dont know if there exist a word in the dictionary thats worse than naive for me to use :roll: )

So thanks for looking
 
Nicholas Jordan
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[H Melua:]   But i dont know how to divide binaries (over Finite fields) to begin with
Try Using cyclotomic polynomials to construct efficient discrete logarithm cryptosystems over finite fields at Springer Berlin / Heidelberg

Note that Bruce Schneier states there are no sufficient texts on crypto, and Springer papers are the only useable source. I just bought Modern Cryptography - Theory and Practice by Wenbo Mao, hp imprint and the author's approach takes a different tone but is substantively similar in it's cautionary admonishments. You can get most such titles at any library: I have asked and been told that this is what the interlibrary loan system is for. All they ask is that you do a reasonable search on your own first and they will obtain any book for you.

Do you want floating point bit-twisting or fixed point ?

There is no such thing as polynom in hex 0xA: There are Polynomials | There are fields, variables, and several Number classes in Java, to do bit-ops, you will likely need to use primitives such as int, which I have seen bit-shifted in the sources for Java. I do not know if fp's could be manipulated.

What you need to do is make *EVERYTHING* BigInteger, and study crypto unabashedly: The work continues, in public, by anyone and everyone who is interested.

[H Melua:]   //i think when we times by x, we actually shift to the right!?

I think we left-shift to mult, but there are sign-extension issues to study and there is also a limitation to the left-shift operator applied to an int that makes << 33 behave something like << 1 (see:0xffffffff leftShift 33 ? )

What is the formal title of your class (schoolastic) and your class (java) and do you intend to become a world-class cryptographer ?
Arjen K. Lenstra1 - Citibank, N.A.,
(Cited Work) show how to use cyclotomic polynomials to construct subgroups of multiplicative groups of finite fields that allow very efficient implementation of discrete logarithm based public key cryptosystems. Depending on the type of application and implementation, the resulting schemes may be up to three times faster than the fastest known schemes of comparable security that use more conventional choices of subgroups or finite fields.
 
H Melua
Ranch Hand
Posts: 172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks "Very" "Very" much for that Nick...
I'll have a good read about this...
Its certainly not a straight-forward task..

Thanks alot for your time again
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!