Vấn đề ở đây là bạn có một ước số $p$ của $n$ của hình thức
$$
p_h \cdot 10^{208} + p_m\cdot 10^{108} + p_l\,,
$$
nơi bạn biết $p_h$ và $p_l$, nhưng không $p_m < 10^{100} \lessapprox
n^{0,16}$.
Rõ ràng, đa thức $f(x) = x\cdot 10^{108} + p_h \cdot 10^{208} + p_l$ sẽ là $0$ modulo $p$ cho bên phải $x = p_m$, được biết là nhỏ. Vì vậy, chúng tôi có thể áp dụng ở đây tổng quát hóa GCD của định lý Coppersmith với $\beta \khoảng 0,5$:
hiền: p_h = 4657466126792836973364876345509106305470210556754730583762574018947035473615496183374863999868029162
hiền giả: p_l = 509718954507298459183080086410468930318128642354235212531127396991917151481316220676314043160415859389810007
sage: n = 8319209622572147564013826542514259498682642243858419574823720424163091461701501360015982209990033336520746744572035014978885083880306655150878826112698449183627604378591045476163815683140601440141181336500755042065319357073688047689369842069576880590382907166998622533395350509313527264108988375924505750514907811200521771091619671861896277515872762861803861776874814818759550176763409337645914659855794895018341028254707583446748584671147839997360735893784761893682319714306096295255392779139228496862261602629668021770766403895493829479280751919607803462139336221636202936115853250410851992088076115853781819064537
hiền triết: P.<x> = Zmod(n)[]
hiền triết: f = x*10^108 + p_h*10^208 + p_l
hiền triết: f = (x*10^108 + p_h*10^208 + p_l)/10^108 # Biến đa thức thành monic
nhà hiền triết: f.small_roots(beta=0.49)
[4555790634870609108348440239954454001363406634260834115187291781797769149826662476501530037286859856]
