Algebraic-group factorisation algorithm (original) (raw)
Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group defined modulo N whose group structure is the direct sum of the 'reduced groups' obtained by performing the equations defining the group arithmetic modulo the unknown prime factors p1, p2, ... By the Chinese remainder theorem, arithmetic modulo N corresponds to arithmetic in all the reduced groups simultaneously.
| Property | Value |
|---|---|
| dbo:abstract | Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group defined modulo N whose group structure is the direct sum of the 'reduced groups' obtained by performing the equations defining the group arithmetic modulo the unknown prime factors p1, p2, ... By the Chinese remainder theorem, arithmetic modulo N corresponds to arithmetic in all the reduced groups simultaneously. The aim is to find an element which is not the identity of the group modulo N, but is the identity modulo one of the factors, so a method for recognising such one-sided identities is required. In general, one finds them by performing operations that move elements around and leave the identities in the reduced groups unchanged. Once the algorithm finds a one-sided identity all future terms will also be one-sided identities, so checking periodically suffices. Computation proceeds by picking an arbitrary element x of the group modulo N and computing a large and smooth multiple Ax of it; if the order of at least one but not all of the reduced groups is a divisor of A, this yields a factorisation. It need not be a prime factorisation, as the element might be an identity in more than one of the reduced groups. Generally, A is taken as a product of the primes below some limit K, and Ax is computed by successive multiplication of x by these primes; after each multiplication, or every few multiplications, the check is made for a one-sided identity. (en) |
| dbo:wikiPageExternalLink | http://gforge.inria.fr/projects/ecm/ |
| dbo:wikiPageID | 14573391 (xsd:integer) |
| dbo:wikiPageLength | 4635 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094213466 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Multiplicative_group dbr:Algebraic_group dbc:Integer_factorization_algorithms dbr:Integer_factorization dbr:Elliptic_curve_method dbr:Quadratic_residue dbr:Elliptic_curve dbr:Greatest_common_divisor dbr:Modular_arithmetic dbr:Hasse's_theorem_on_elliptic_curves dbr:Inverse_function dbr:Chinese_remainder_theorem dbr:Smooth_number dbr:Williams'_p_+_1_algorithm dbr:Pollard's_p-1_algorithm dbr:Binary_exponentiation |
| dbp:wikiPageUsesTemplate | dbt:Unreferenced |
| dcterms:subject | dbc:Integer_factorization_algorithms |
| gold:hypernym | dbr:Algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatIntegerFactorizationAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group defined modulo N whose group structure is the direct sum of the 'reduced groups' obtained by performing the equations defining the group arithmetic modulo the unknown prime factors p1, p2, ... By the Chinese remainder theorem, arithmetic modulo N corresponds to arithmetic in all the reduced groups simultaneously. (en) |
| rdfs:label | Algebraic-group factorisation algorithm (en) |
| owl:sameAs | freebase:Algebraic-group factorisation algorithm yago-res:Algebraic-group factorisation algorithm wikidata:Algebraic-group factorisation algorithm https://global.dbpedia.org/id/4NPMa |
| prov:wasDerivedFrom | wikipedia-en:Algebraic-group_factorisation_algorithm?oldid=1094213466&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Algebraic-group_factorisation_algorithm |
| is dbo:wikiPageRedirects of | dbr:Algebraic-group_factorisation_algorithms dbr:Algebraic-group_factorization_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Pollard's_p_−_1_algorithm dbr:Algebraic-group_factorisation_algorithms dbr:Algebraic-group_factorization_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Algebraic-group_factorisation_algorithm |