About: Algebraic-group factorisation algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Algebraic-group factorisation algorithm Goto Sponge NotDistinct Permalink

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

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.

Attributes	Values
rdfs:label	Algebraic-group factorisation algorithm (en)
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)
sameAs	Algebraic-group factorisation algorithm Algebraic-group factorisation algorithm
dbp:wikiPageUsesTemplate	dbt:Unreferenced
Subject	Integer factorization algorithms
Link from a Wikipage to an external page	http://gforge.inria.fr/projects/ecm/
gold:hypernym	Algorithms
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Algebraic-group_factorisation_algorithm?oldid=994038110&ns=0
Wikipage page ID	14573391 (xsd:integer)
page length (characters) of wiki page	4635 (xsd:nonNegativeInteger)
Wikipage revision ID	994038110 (xsd:integer)
Link from a Wikipage to another Wikipage	Greatest common divisor Smooth number Algebraic group Integer factorization algorithms Lenstra elliptic-curve factorization Quadratic residue Chinese remainder theorem Elliptic-curve cryptography Exponentiation by squaring Hasse's theorem on elliptic curves Integer factorization Inverse function Modular arithmetic Multiplicative group Pollard's p − 1 algorithm Williams's p + 1 algorithm
has 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)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Algebraic-group_factorisation_algorithm
is Wikipage redirect of	Algebraic-group factorisation algorithms Algebraic-group factorization algorithm
is Link from a Wikipage to another Wikipage of	Integer factorization Algebraic-group factorisation algorithms Algebraic-group factorization algorithm
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Algebraic-group_factorisation_algorithm

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

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, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software