가장 작은 소수를 찾는 함수

PARI/GP는 t_INT의 가장 작은 소수 요소를 찾거나 정수의 부분 분해를 수행하는 함수가 있습니까? 예를 들어가장 작은 소수를 찾는 함수

, 나는 수있는 경우 :

a=261432792226751124747858820445742044652814631500046047326053169701039080900441047539208779404889565067

이 a 두 개의 큰 소인수를 포함 factor(a) 때문에 할 시간이 오래 걸립니다. 그러나 17은 a의 약수임을 쉽게 알 수 있습니다.

물론이 경우에는 요인을 찾기 위해 forprime(p=2,,a % p == 0 && return(p)) 또는 이와 유사한 평가판을 사용할 수있었습니다. 그러나 최소한의 요소가 20 개의 십진수를 가지고 있다면, 그것은 비현실적 일 것이고, 나는이 경우에 factor라는 정교한 방법을 사용하고 싶었을 것입니다.

내가 어떤 부분 인수 분해에 만족하실 것입니다 말, 또는 등, 내가 걱정하는 모든 작은 적지 않은 제수 것을

출처

2017-10-19 Jeppe Stig Nielsen

(작은 요인을 전문으로하는) [Lenstra 타원 곡선 분해] (https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization)의 변형에 대해 생각해 보셨습니까? 일단 어떤 요인을 발견하면 휴식을 취하기 위해 그것을 수정할 수 있습니다. –

@JosephWood PARI의'factor' 또는'factorint' 함수는 이미 접근법 중 하나로서 타원 곡선 메서드를 사용합니다. 내 타원 곡선 구현을 코딩 할 수 있다는 것을 알고 있지만, PARI/GP에 내장 된 것이 있는지 묻고있었습니다. –

PARI 라이브러리는 유용 할 수있는'Z_factor_until' 함수를 가지고 있습니다. 그러나 가장 작은 소수 요소를 찾았 음을 증명하는 것이 일반적으로 쉽지는 않지만 하나의 옵션을 선택하십시오 : 특정 숫자에서만 작동하고, 확실한 것보다는 '가능성이 높습니다'. 긴 실행 시간; 작은 숫자에서만 작동합니다. – Charles

말 플래그의 일종으로 factor를 호출 할 수 있다면 이상적 일 것이다 그래서 내 질문에 아주 간단한 부분적인 대답은 factor는 선택적 인수 lim을 가지고 있다는 것입니다, 그래서 당신은 말을 바로 할 수 있습니다 10^5 아래

예를 들어

factor(a, 10^5)

, 단지 요인 (결과에 이상 10^5 수 보조인이 나타납니다 합성해라!).

factorint의 선택적 인수는 비트 방식의 "플래그"와 완전히 다르며 제한을 지정할 수 없습니다. 그게 아마도 나를 혼란스럽게 만들었을 것이다. 예를 들어 :

factorint(a, 1+8)

이 플래그를 선택 1 ("최종 ECM을 실행하지 않습니다") ("MPQS을 피")와 8.

출처

2017-10-20 12:45:49

답변

관련 문제