Challenge

from Crypto.Util.number import getPrime, isPrime, bytes_to_long


p=getPrime(512)
while True:
	w=getPrime(20)
	x=2*w*p-1
	if isPrime(x):
		break

q=getPrime(512*2)
n = p * q *x
e = 65537
m = bytes_to_long(b'redacted')
c = pow(m, e, n)
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")


'''
n = 18186672849609603331344182584568642941078893104802301217241028624469607021717197485036251613075846729705028441094100248337306406098776983108141004863456595015660485098203867670995838502297993710897784135087115777697925848407153788837657722171924264421550564295047937036911411846582733847201015164634546149603743246378710225407507435371659148999942913405493417037116587298256802831009824832360479040621348157491754407277404391337488226402711686156101028879269050800874367763551119682177453648890492731413760738825931684979379268401715029193518612541590846238434595210876468090976194627398214837801868969047036272502669215123
e = 65537
c = 1617999293557620724157535537778741335004656286655134597579706838690566178453141895621909480622070931381931296468696585541046188947144084107698620486576573164517733264644244665803523581927226503313545336021669824656871624111167113668644971950653103830443634752480477923970518891620296211614968804248580381104245404606917784407446279304488720323993268637887493503760075542578433642707326246816504761740168067216112150231996966168374619580811013034502620645288021335483574561758204631096791789272910596432850424873592013042090724982779979496197239647019869960002253384162472401724931485470355288814804233134786749608640103461
'''


Solve

https://en.wikipedia.org/wiki/Williams's_p_%2B_1_algorithm

This challenge is actually a special case, where p is a factor of n but also a factor of x+1.

So we can include the line v = mlucas(v,n,n) because n is a multiple of p.


from math import gcd
from tqdm import tqdm
from gmpy2 import next_prime

def mlucas(v, a, n):
    v1, v2 = v, (v**2 - 2) % n
    for bit in bin(a)[3:]:
        if bit == "0":
            v1, v2 = (v1**2 - 2) % n, (v1*v2 - v) % n
        else:
            v1, v2 = (v1*v2 - v) % n, (v2**2 - 2) % n
    return v1

primes = []
p = next_prime(2**19)
while p < 2**20:
    primes.append(p)
    p = next_prime(p)

def factor(n):
    for v in range(3, 100):
        v = mlucas(v,2,n)
        v = mlucas(v,n,n)
        for p in tqdm(primes):
            v = mlucas(v,p,n)
            g = gcd(v - 2, n)
            if g != 1:
                return g

n = 18186672849609603331344182584568642941078893104802301217241028624469607021717197485036251613075846729705028441094100248337306406098776983108141004863456595015660485098203867670995838502297993710897784135087115777697925848407153788837657722171924264421550564295047937036911411846582733847201015164634546149603743246378710225407507435371659148999942913405493417037116587298256802831009824832360479040621348157491754407277404391337488226402711686156101028879269050800874367763551119682177453648890492731413760738825931684979379268401715029193518612541590846238434595210876468090976194627398214837801868969047036272502669215123
e = 65537
c = 1617999293557620724157535537778741335004656286655134597579706838690566178453141895621909480622070931381931296468696585541046188947144084107698620486576573164517733264644244665803523581927226503313545336021669824656871624111167113668644971950653103830443634752480477923970518891620296211614968804248580381104245404606917784407446279304488720323993268637887493503760075542578433642707326246816504761740168067216112150231996966168374619580811013034502620645288021335483574561758204631096791789272910596432850424873592013042090724982779979496197239647019869960002253384162472401724931485470355288814804233134786749608640103461
p = factor(n)
print(bytes.fromhex(f'{pow(c, pow(e, -1, p-1), p):x}'))




Some more generalised testing and speedup

from Crypto.Util.number import getPrime, isPrime, bytes_to_long


p=getPrime(512)
while True:
    w = getPrime(20)
    assert w < 2**20
    x=2*w*p-1
    if isPrime(x):
        break

q=getPrime(512*2)
n = p * q *x
e = 65537
m = bytes_to_long(b'redacted')
c = pow(m, e, n)


###

from math import gcd
from tqdm import tqdm
from gmpy2 import next_prime, lucasv_mod

def mlucas(v, a, n):
    return lucasv_mod(v, 1, a, n) # faster

primes = []
p = next_prime(2**19)
while p < 2**20:
    primes.append(p)
    p = next_prime(p)

def factor(n):
    for v in range(3, 100):
        v = mlucas(v,2,n)
        v = mlucas(v,n,n)
        for p in tqdm(primes):
            v = mlucas(v,p,n)
            g = gcd(v - 2, n)
            if g != 1:
                return g

p = factor(n)
print(bytes.fromhex(f'{pow(c, pow(e, -1, p-1), p):x}'))