This HTML5 document contains 48 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n16http://gforge.inria.fr/projects/ecm/
n15https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Algebraic-group_factorisation_algorithm
rdf:type
yago:Act100030358 yago:Algorithm105847438 yago:Abstraction100002137 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatIntegerFactorizationAlgorithms yago:Event100029378 yago:Activity100407535 yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:label
Algebraic-group factorisation algorithm
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.
dct:subject
dbc:Integer_factorization_algorithms
dbo:wikiPageID
14573391
dbo:wikiPageRevisionID
1094213466
dbo:wikiPageWikiLink
dbr:Multiplicative_group dbr:Hasse's_theorem_on_elliptic_curves dbr:Algebraic_group dbr:Smooth_number dbr:Elliptic_curve_method dbr:Modular_arithmetic dbr:Binary_exponentiation dbr:Chinese_remainder_theorem dbr:Elliptic_curve dbc:Integer_factorization_algorithms dbr:Quadratic_residue dbr:Pollard's_p-1_algorithm dbr:Integer_factorization dbr:Inverse_function dbr:Williams'_p_+_1_algorithm dbr:Greatest_common_divisor
dbo:wikiPageExternalLink
n16:
owl:sameAs
freebase:m.03d8bcr wikidata:Q4723979 yago-res:Algebraic-group_factorisation_algorithm n15:4NPMa
dbp:wikiPageUsesTemplate
dbt:Unreferenced
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.
gold:hypernym
dbr:Algorithms
prov:wasDerivedFrom
wikipedia-en:Algebraic-group_factorisation_algorithm?oldid=1094213466&ns=0
dbo:wikiPageLength
4635
foaf:isPrimaryTopicOf
wikipedia-en:Algebraic-group_factorisation_algorithm
Subject Item
dbr:Pollard's_p_−_1_algorithm
dbo:wikiPageWikiLink
dbr:Algebraic-group_factorisation_algorithm
Subject Item
dbr:Algebraic-group_factorisation_algorithms
dbo:wikiPageWikiLink
dbr:Algebraic-group_factorisation_algorithm
dbo:wikiPageRedirects
dbr:Algebraic-group_factorisation_algorithm
Subject Item
dbr:Algebraic-group_factorization_algorithm
dbo:wikiPageWikiLink
dbr:Algebraic-group_factorisation_algorithm
dbo:wikiPageRedirects
dbr:Algebraic-group_factorisation_algorithm
Subject Item
wikipedia-en:Algebraic-group_factorisation_algorithm
foaf:primaryTopic
dbr:Algebraic-group_factorisation_algorithm