About: Kunerth's algorithm     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

Kunerth's algorithm is an algorithm to determine the modular square root of a number.The algorithm does not require the factorization of the modulus, and only has one modular operation that is often easy if the cipher is a prime. To find do the following steps The hard step is the solving of the quadratic equation, but if this can be done then the algorithm quickly finds the modular square root without much computation.

AttributesValues
rdfs:label
  • Kunerth's algorithm (en)
rdfs:comment
  • Kunerth's algorithm is an algorithm to determine the modular square root of a number.The algorithm does not require the factorization of the modulus, and only has one modular operation that is often easy if the cipher is a prime. To find do the following steps The hard step is the solving of the quadratic equation, but if this can be done then the algorithm quickly finds the modular square root without much computation. (en)
dbp:wikiPageUsesTemplate
Subject
prov:wasDerivedFrom
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
Link from a Wikipage to another Wikipage
has abstract
  • Kunerth's algorithm is an algorithm to determine the modular square root of a number.The algorithm does not require the factorization of the modulus, and only has one modular operation that is often easy if the cipher is a prime. To find do the following steps 1) find the modular square root of This step is quite easy, no matter how big the original modulus is, if is a prime.2) solve a quadratic equation associated with the modular square root of . Most of Kunerth's examples in his original paper solve this equation by having C be a natural square and thus setting z to zero.Expand out the following equation to obtain the quadraticif thenYou can always ensure that the quadratic can be solved by adjusting the N term(modulus) in the above equation. Thuswill ensure a quadratic of You can then adjust F to ensure that C+F is a square. Quite large modula, such as can have their square roots taken quickly via this method.The parameters of the polynomial expansion are quite fluid, in that can be done, for instance. It is quite easy to set X and Y so that is a square. The modular square root of can be taken this way.3) Having solved the associated quadratic equation we now have the variables w and set v=r (if C in the quadratic is a natural square).4) Solve for two more variables, alpha and beta by the following equationalpha == w (v + w beta )Please note that this is not a modular operation and that alpha and beta could have many paired answers.5) Obtain a value for X via a factorization of the following polynomial.obtaining an answer like(-37 + 9 x) (1 + 25 x)6) Obtain the modular square root by the equation. Remember to set X so that the term above is zero. Thus X would be 37/9 or -1/25. The hard step is the solving of the quadratic equation, but if this can be done then the algorithm quickly finds the modular square root without much computation. (en)
foaf:isPrimaryTopicOf
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git151 as of Feb 20 2025


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software