WWB w,BAO +,5A+WAW5 #
,5A A,OW"N,5 W NwAWw,55 5,+O
5A+A,BW,5
aL i  + 6L?L**L @ @?_ ,*L @|**i
Aw #iT| Lu 5}?@* AiLh) @?_ L44?U@|L?  N?ih |@| L*|iU?U@ _i @|@*?)@
U% aLh_ BhL?@  ,_U #D @hUi*L?@ H ec 5W
i4@*G @_h@?9}T | UTUi
DEVWUDFW
Pxowlsoh0sd hdu k wudwhjlh duh d qh h du| k l h
w uhgx h wkh psxwdwl qdo w dqg php u| uh0
xluhphqw i odujh y dexodu| shh k uh jqlwl q
| whp xl qj glhuhqw nlqg u psoh{ p ghoolqj
i shh k dqg odqjxdjh1 Lq wkh Q0eh w dssu d k
wkh p w h lhqw nq zohgjh xu h +x xdoo| d x wl
p gho dqg d el2wuljudp odqjxdjh p gho, duh x hg
u w w hoh w d k uw ol w +Q0eh w, i dowhuqdwlyh k|0
s wkh h 1 Wkhq/ wkh uhpdlqlqj p uh psoh{ nq zo0
hgjh xu h duh x hg w uh uh wkh h xhq h 1 Lq
wkl sdshu zh su s h d qhz doj ulwkp w yhu ph
wkh su eohp d ldwhg zlwk wkh lpsoh %Wud hed n0
Ed hg% Q0eh w doj ulwkp zkloh q huylqj lw lpsol 0
lw| dqg o z psxwdwl qdo w1
4 LQWURGXFWLRQ
Wkl sdshu suh hqw d qhz Q0eh w hdu k doj ulwkp
ed hg q wkh pelqdwl q i wz zhoo0nq zq wh k0
ql xh lq qwlqx x shh k uh jqlwl q= judppdu
wkdw lps h d uh wul wl q lq wkh ohqjwk +qxpehu i
z ug , i wkh uh jql}hg h xhq h ^6` dqg wkh wdq0
gdug wud hed n0ed hg Q0eh w doj ulwkp ^7/ 8/ :`
Pxowlsoh0sd hdu k wudwhjlh duh d pp q
k l h w uhgx h wkh psxwdwl qdo w dqg php0
u| uh xluhphqw i odujh0y dexodu| shh k uh jql0
wl q | whp ^:`1 Lq wkh Q0eh w dssu d k wkh p w
h lhqw nq zohgjh xu h +x xdoo| d x wl p gho
dqg d el2wuljudp odqjxdjh p gho, duh x hg u w w
hoh w d k uw ol w +Q0eh w, i dowhuqdwlyh k|s wkh0
h 1 Wkhq/ wkh uhpdlqlqj p uh psoh{ nq zohgjh
xu h +o qj0gl wdq h uhodwl q ehwzhhq z ug / odq0
jxdjh xqghu wdqglqj p gho / ydolg whohsk qh u uhglw
dug qxpehu / su g|/ 111, duh x hg w uh uh dqg
uh ughu wkh Q0eh w k|s wkh h zlwk d uhd qdeoh p0
sxwdwl qdo h uw1
Hyhq li zh d xph glhuhqw k|s wkh h kdyh ljqli0
l dqwo| glhuhqw uh / wkh h{d w Q0eh w doj ulwkp l
i olwwoh sud wl do lqwhuh w eh dx h i lw psxwdwl qdo
w1 Wkhuhi uh/ hyhudo dssu {lpdwh doj ulwkp kdyh
A hi i@hU @ TTLh|i_ M) |i W A 5T@?  hi
i@hU ThLiU| AWbH SH
ehhq ghyho shg1 Wkh lpsoh w dqg ohd w h{shq lyh do0
j ulwkp i u qglqj wkh Q0eh w k|s wkh h l qh wkdw
lpso| x h wkh wud hed n lqi updwl q i wkh wdqgdug
qh0sd doj ulwkp ^4/ 5/ 9`1 Wkh wud hed n0ed hg Q0
eh w doj ulwkp uh xluh dop w q h{wud psxwdwl q
uh sh w w wkh wdqgdug qh0sd doj ulwkp1 K zhyhu/
lq hoh wlqj wkh Q0eh w k|s wkh h lw x xdoo| pl h u
xqghuh wlpdwh kljk uhg qh 1
Wkh wud hed n0ed hg Q0eh w doj ulwkp qo| nhhs
qh sdwk zlwklq d z ug dqg pxowlsoh k|s wkh h duh
q lghuhg qo| lq wkh wudq lwl q ehwzhhq z ug 1 K|0
s wkh h i glhuhqw ohqjwk d % qh wz wkuhh% dqg
% qh wkuhh% duh qhyhu lpxowdqh x o| q lghu e| wkh
wud hed n0ed hg Q0eh w doj ulwkp hyhq li e wk kdyh
dop w wkh dph su edelolw| dqg zh q lghu d odujh
qxpehu i k|s wkh h 1 Vhyhudo dssu d kh i p0
su pl h ehwzhhq wkh h{d w Q0eh w dqg wkh wud hed n0
ed hg doj ulwkp kdyh ehhq su s hg lq wkh olwhudwxuh
w oyh wkdw su eohp1 K zhyhu wkh su s hg doj 0
ulwkp x xdoo| uhsuh hqw d ljql dqw lq uhd h lq wkh
psxwdwl qdo w u php u| uh xluhphqw uh sh w
w wkh ed l doj ulwkp1
Wkh dssu d k su s hg lq wkl sdshu pelqh wkh
wud hed n0ed hg Q0eh w doj ulwkp zlwk wkh ohqjwk uh0
wul wl q lps hg e| d lpsoh judppdu w i u h wkh
lq ox l q i h xhq h i glhuhqw ohqjwk lq wkh h0
oh whg ol w i z ug h xhq h 1 Wkh h nlqg i judp0
pdu duh x xdo lq wd n d qqh whg gljlw uh jqlwl q
lq zkl k wkh h{sh whg qxpehu i gljlw pd| eh i u hg
e| d qlwh0 wdwh judppdu1 Vlq h pxowlsoh lq huwl q
u ghohwl q duh q w su edeoh/ wkh judppdu l x xdoo|
lpsolhg w q lghu h xhq h i ohqjwk Nq.pi u
dq| q/ zkhuh Nkd d pdoo {hg ydoxh dqg pudqjh
iu p 3 w N41
Lq wkh uh xow suh hqwhg khuh zh kdyh q lghuhg
ydoxh i Nlq wkh udqjh iu p 4 w 8/ lq pelqdwl q
zlwk wkh wud hed n0ed hg Q0eh w doj ulwkp zlwk xs
w 533 k|s wkh h shu hqwhq h1
Wkh i oo zlqj h wl q jlyh p uh ghwdlo de xw wkh
su s hg doj ulwkp1 Wkhq/ zh suh hqw wkh uh xow e0
wdlqhg lq wz glhuhqw wd n = wkh uh jqlwl q i q0
qh whg gljlw dqg wkh uh jqlwl q i qxpehu 1
5 H[WHQGHG WUDFHEDFN0EDVHG
Q0EHVW DOJRULWKP
Wkh lpsoh w dqg ohd w h{shq lyh doj ulwkp i u e0
wdlqlqj pxowlsoh k|s wkh h zd u w su s hg lq
^7/ 8` d d p gl dwl q i wkh qh0sd doj ulwkp1 D
lq wkh wdqgdug qh0sd doj ulwkp/ lq wkl Q0eh w do0
j ulwkp zh qo| nhhs qh wkh u| dw hd k z ug wdwh1
K zhyhu/ dw hd k judppdu q gh/ wkh wud hed n lqi u0
pdwl q l h{whqghg w w uh q w qo| wkh lqgh{ dqg
uh i wkh eh w ulqj z ug/ exw do wkh lqgh{h
dqg uh i wkh qeh w0 ulqj z ug 1 Dw wkh hqg i
wkh h xhq h/ wkh dyhg wud hed n lqi updwl q l x hg
w uh xu lyho| jhqhudwh wkh Q eh w dq zhu 1
Wkl p gl dwl q xss h d qhjoljleoh lq uhd h lq
wkh psxwdwl qdo w de yh wkh wdqgdug qh0sd
doj ulwkp1 K zhyhu/ wkl lpsol lw| l do wkh dx h
i qh lps uwdqw gudzed n1 Vlq h wkl wud hed n0
ed hg doj ulwkp nhhs qo| qh wkh u| d hd k wdwh/ lw
| whpdwl doo| pl h ph kljk ulqj k|s wkh h 1
I u h{dpsoh/ ohw x q lghu d lpsoh wd n d q0
qh whg gljlw uh jqlwl q1 Li wkh eh w k|s wkh l l
% qh wkuhh%/ wkh wdqgdug wud hed n0ed hg doj ulwkp
zloo q w eh deoh w jhqhudwh wkhu k|s wkh h ehjlq0
qlqj zlwk wkh z ug % qh% dqg hqglqj zlwk wkh z ug
%wkuhh%1 Wkdw l / hyhq li wkh hqwhq h % qh wz wkuhh%
kd dop w wkh dph su edelolw|/ lw zloo qhyhu dsshdu
lq wkh ol w i wkh qeh w jhqhudwhg k|s wkh h 1 Wkl
l eh dx h zh nhhs qo| qh s| i hd k z ug wdwh1
Wkhuh l qo| qh eh w ehjlqqlqj wlph i u wkh hqglqj
z ug %wkuhh%/ dqg qo| qh eh w hqglqj wlph i u wkh
u w z ug % qh%1
Lq wkh su s hg h{whq l q i wkh wdqgdug doj 0
ulwkp/ wkl su eohp l oyhg zlwk wkh dgglwl q i d
judppdu wkdw i u h wkh q lghudwl q i h xhq h i
glhuhqw ohqjwk lq wkh Q0eh w hdu k1 Iljxuh 4 k z
wkh 60 wdwh judppdu wkdw q lghu h xhq h i 6q.l
z ug dwhd kq ghl> i u dq| dueulwdu| q1
Lq jhqhudo/ wkh su s hg Q0Eh w doj ulwkp dgg d
judppdu i N wdwh w wkh wud hed n0ed hg Q0eh w
doj ulwkp i u qqh whg z ug uh jqlwl q1 Wkl lp0
soh judppdu i u h wkh q lghudwl q i glhuhqw ol w
i k|s wkh h dw hd k i wkh Nq gh 1 Lq wkh lpsoh0
phqwdwl q i wkh su s hg doj ulwkp q lghuhg khuh/
wkh h{whqghg Q0Eh w doj ulwkp zloo nhhs d hsdudwh
ol w zlwk wkh Q0eh w z ug h xhq h i ohqjwk qN.ldw
hd k judppdu q gh l1 Dw wkh hqg i wkh h xhq h/ zh
zloo hoh w wkh qo| Q0Eh w jo edo k|s wkh h dp qj
wkh w wdo NQk|s wkh h w uhg lq doo wkh judppdu
q gh 1
Wkh su s hg doj ulwkp pxowlsolh e| Nwkh hdu k
sd h/ lq h lw nhhs d glhuhqw z ug wdwh wkh u| dw
hd k judppdu q gh1 K zhyhu/ lq sud wl h/ wkh su 0
s hg doj ulwkp g h q w x xdoo| uhsuh hqw d ljqli0
l dqw lq uhd h lq wkh w wdo psxwdwl qdo w li zh
lq oxgh d suxqlqj wh kql xh d wkh ehdp hdu k lq
xu hdu k1
Li wkh i oo zlqj h wl q zh k z k z wkh su s hg
h{whqghg Q0eh w doj ulwkp pd| eh x hixo lq ph
uh jqlwl q wd n 1 Zh zloo do lq oxgh uh xow p0
sdulqj wkh shui updq h dqg psxwdwl qdo w i
wkh su s hg doj ulwkp zlwk uh sh w w wkh wdqgdug
+N@ 4, Q0eh w doj ulwkp i u qqh whg z ug uh j0
qlwl q1
6 UHVXOWV
Vhyhudo uh jqlwl q h{shulphqw zhuh qgx whg lq u0
ghu w hydoxdwh wkh shui updq h i wkh su s hg Q0
eh w doj ulwkp1 Lq wkl sdshu zh suh hqw wkh uh xow
ewdlqhg lq wz lpsoh wd n = qqh whg gljlw dqg
qxpehu uh jqlwl q11
Wkh sdudphwhu wkdw ghqh wkh pp q h wl q
i wkh uh jql}hu duh wkh i oo zlqj=
0 Vdpsolqj Iuh xhq |= ;333 dpsoh 2
0 Zlqg z l}h= 63 p 1
0 Zlqg z gl sod hphqw= 43 p 1
0 Sdudphwhul}dwl q= 47 PIFF h lhqw zlwk hs0
wudo oliwhulqj dqg 53 edqn owhu 1 Uhdo0wlph hs wudo
phdq xe wud wl q1
0 Ghowd iudph = 5
0 D hohudwl q iudph = 4
614 Wd n 41 F qqh whg gljlw uh jqlwl q
Lq wkl u w h{shulphqw/ zh q lghu wkh uh jqlwl q
i gljlw wulqj x lqj zk oh z ug p gho i u wkh whq
Vsdql k gljlw sox d p gho i wkh lohq h2q l h1 W
wudlq wkh KPP p gho i wkh gljlw zh x h sduw i wkh
Vshh kGdw ^<` Vsdql k Il{hg Qhwz un F usx / zkloh
i u wh wlqj zh q lghuhg d glhuhqw gdwded h zlwk
4533 gljlw wulqj i glhuhqw ohqjwk 1
Khuh/ zh wxglhg wkh xpxodwlyh shu hqw i uuh w
wulqj d d ixq wl q i wkh qxpehu Q i k|s wkh h
dqg wkh qxpehu N i judppdu wdwh 1 Wkh uh xow
duh i gluh w lqwhuh w i u dssol dwl q zkhuh wkh ol w i
ydolg gljlw wulqj l uh wul whg w d qlwh hw/ u wkh
wulqj lq oxgh ph nlqg i huu u0ghwh wlqj u huu u0
uuh wlqj gl dwl q1
Iljxuh 5 k z wkh shu hqw i uuh w wulqj wkdw
zhuh pl lqj lq wkh jhqhudwhg Q0eh w h xhq h i u
glhuhqw qxpehu i judppdu q gh / N@4/N@5
dqg N@ 81 Wkh uh xow i u N@5dqgN@8
k z d ohdu lpsu yhphqw zlwk uh sh w w wkh wdq0
gdug wud hed n0ed hg Q0eh w doj ulwkp +N@4,lizh
q lghu d odujh qxpehu i k|s wkh h 1 Lq wkl h{shu0
lphqw/ zh kdyh 44 z ug p gho +43 gljlw . q l h,
lq sdudooho lq hd k q gh i wkh judppdu1 Vlq h zh
q lghu wkh p gho i wkh lohq h lq sdudooho zlwk wkh
p gho i wkh gljlw / wkhuh l q gluh w uhodwl q eh0
wzhhq wkh judppdu q gh dqg wkh qxpehu i gljlw lq
wkh k|sk wh h / l1h1/ zh dq kdyh h xhq h zlwk }hu /
qh u p uh lohq h *z ug *1 Lq id w/ p w i wkh k|0
sk wh h qo| glhu lq wkh qxpehu dqg2 u s lwl q i
wkh lohq h *z ug *1
Iljxuh 6 psduh wkh qxpehu i h qg uh xluhg
w su h wkh wh w gdwded h/ d d ixq wl q i wkh qxp0
ehu i judppdu wdwh dqg wkh qxpehu i k|s wkh h 1
I u N@ 5/ wkh w wdo psxwdwl qdo w l lplodu w
wkh w i wkh wdqgdug doj ulwkp +N@4,1
615 Wd n 51 Uh jqlwl q i qxpehu
Lq wkl h{shulphqw/ zh wxglhg wkh uh jqlw q i
odujh xuuhq | p qh| dp xqw +juhdwhu wkdq qh plo0
ol q,1 D ed holqh zh q lghuhg d lpsoh qqh whg
z ug uh jqlwl q | whp zlwk xw dq| nlqg i judp0
pdu +qxpehu jhqhudwl q judppdu u q0judp p g0
ho ,1 Wkh y dexodu| q l whg i :3 z ug +xq / g /
wuh / yhlqwlxq / yhlqwlg / wuhlqwd/ wuhlqwd |/ lhq/ g 0
lhqw / plo/ xq ploo q/ sh hwd / 111, uhdwhg iu p
ghplsk qh p gho ^;`1 Wkh ghplsk qh p gho zhuh
wudlqhg x lqj sduw i wkh sk qhwl doo|0ul k hqwhq h
i wkh Vshh kGdw gdwded h1 Wkh 958 qxpehu i wh w
zhuh hoh whg iu p wkh dph gdwded h1
I u wkl wd n/ zh wxglhg li wkh judppdu0iuhh uh j0
qlwl q | whp zd deoh w su ylgh wkh uuh w dq0
zhu/ dqg li wkh uuh w dq zhu zd wkh u w k|s wk0
h l judppdwl doo| uuh w1 Wkl judppdu0iuhh | 0
whp zd lqwhqwl qdoo| w lpsoh w su ylgh uh xow
i sud wl do lqwhuh w lq dq| d h1 Wkh sxus h i wkh
h{shulphqw zd mx w w wxg| wkh ehkdyl xu i wkh
glhuhqw doj ulwkp 1
Wkh uh xow i wkh ed holqh | whp +Q@4>N @4,
d zhoo d wkh uh xow ewdlqhg zlwk wkh wdqgdug dqg
wkh h{whqghg wud hed n0ed hg doj ulwkp Q0eh w duh
suh hqwhg lq wdeoh 41 Zh q lghuhg wkdw wkh uh j0
ql}hu zd su ylglqj d uuh w dq zhu zkhq wkh u w
k|sk wh l uuh s qglqj w d lqjoh judppdwl doo|0
uuh w qxpehu zd uuh w1 Li wkl u w qxpehu zd
q w uuh w zh kdg dq huu u1 Li wkh uh jql}hu glg
q w su ylghg dq| judppdwl doo|0 uuh w qxpehu/ zh
q lghuhg wkh hqwhq h d uhmh whg1
Q N uuh w huu u uhmh whg
44 593 :7 5<4
43 4 673 457 494
43 5 665 43< 4;7
433 4 693 4;: :;
433 5 69; 499 <4
Wdeoh 41 F psdul q i wkh uh xow ewdlqhg
e| wkh ed holqh | whp +Q@4>N @4,/
wkh wdqgdug wud hed n0ed hg Q Eh w doj 0
ulwkp +QA4>N @ 4,/ dqg wkh su s hg
doj ulwkp +N@ 5,1 D qxpehu l uhmh whg
li wkh uh jql}hu l g h q w jhqhudwh d
judppdwl doo|0 uuh w k|s wkh l 1
Wkh uh xow lqgl dwh wkdw wkh su s hg Q0Eh w do0
j ulwkp zlwk N@ 5 uhgx h wkh qxpehu i lq uuh w
uh jql}hg qxpehu iu p 457 +N@4,w 43</zkhq
zh q lghu wkh u w 43 k|s wkh h / +Q@43,1 Zh
dq do e huyh wkdw lq uhd lqj wkh qxpehu i k|0
sk wh h iu p 43 w 433 su gx hg px k p uh zu qj
k|s wkh h
7 FRQFOXVLRQV
Wkl sdshu wxglhg wkh pelqdwl q i wz zhoo0
nq zq wh kql xh lq shh k uh jqlwl q= judppdu
wkdw lps h d uh wul wl q lq wkh ohqjwk +qxpehu i
z ug , i wkh uh jql}hg h xhq h dqg wkh wud hed n0
ed hg Q0eh w doj ulwkp1 Wkh su s hg doj ulwkp do0
ohyldwh wkh su eohp i wkh wdqgdug wud hed n0ed hg
Q0eh w doj ulwkp/ zkloh nhhslqj lw lpsol lw|1
Wkh uh xow lq wd n d uh jqlwl q i gljlw wulqj
dqg qxpehu iu p wkh Vsdql k Vshh kGdw Gdwded h
^<` lqgl dwh wkdw wkh su s hg doj ulwkp l d j g
k l h i u uhdo0wlph dssol dwl q 1 Wkh doj ulwkp
kd ehhq douhdg| hoh whg i u pphu ldoo| dydlodeoh
shh k uh jqlwl q | whp dqg dssol dwl q 1
Uhihuhq h
^4` W1N1 Ylqw |xn1 %Hohphqw0Zl h Uh jqlwl q i
F qwlqx x Vshh k F q l wlqj i Z ug Iu p
d Vsh lhg Y dexodu|/% Nlehuqhwl d +F|ehuqhw0
l ,/ Q 1 5/ ss1 4660476/ Pdu k0Dsulo 4<:41
^5` K1 Qh|1 %Wkh X h i d Rqh0Vwdjh G|qdpl Su 0
judpplqj Doj ulwkp i u F qqh whg Z ug Uh j0
qlwl q/% LHHH Wudq 1 D x wl / Vshh k/ Vljqdo
Su 1/ Y o1 65/ q 1 5/ ss 59605:4/ Dsulo 4<;71
^6` F1K1 Ohh dqg O1 Udelqhu/ %D Iudph0V|q ku q x
Qhwz un Vhdu k Doj ulwkp i u F qqh whg0Z ug
Uh jqlwl q/% LHHH Wudq 1 D x wl / Vshh k/
Vljqdo Su 1/ Y o1 6:/ q 1 44/ ss 497<0498;/ Q 0
yhpehu 4<;<1
^7` M1E1 Pdulq dqg H1 P qwh1 %Jhqhudwl q i Pxo0
wlsoh K|s wkh l lq F qqh whg Sk qhwl 0Xqlw
Uh jqlwl q e| d P glhg Rqh0Vwdjh G|qdpl
Su judpplqj Doj ulwkp/% Su 1 Hxu shh k ;</
Y o1 5/ ss173;07441 Sdul / Vhswhpehu 4<;<1
^8` Y1 Vwhlqel 1 %Vhqwhq h0K|s wkh h Jhqhudwl q lq
d F qwlqx x 0Vshh k Uh jqlwl q V| whp/% Su 1
Hxu shh k ;</ Y o1 5/ ss1840871 Sdul / Vhswhp0
ehu1 4<;<1
^9` Odzuhq h Udelqhu/ Ellqj0Kzdqj Mxdqj1 Ixqgd0
phqwdo i Vshh k Uh jqlwl q1 Suhqwl h Kdoo 4<<61
^:` U1 V kzduw}/ O1 Qjx|hq dqg M1 Pdnk xo1
%Pxowlsoh0Sd Vhdu k Vwudwhjlh %1 Lq Dxw pdwl
Vshh k dqg Vshdnhu Uh jqlwl q/ Noxzhu D dg0
hpl 4<<91 Fkdswhu 4;1
^;` M hE1Pdulq / D1 Q jxhuld dqg D1 E qd0
i qwh1 %Wkh ghplsk qh= dq h lhqw xez ug xqlw
i u qwlqx x shh k uh jqlwl q/% Su 1 HX0
URVSHHFK*<:/ ss1 45480454;/ Uk gh / Vhswhp0
ehu 4<<:1
^<` Vshh kGdw LL1 Vshh k Gdwded h i u wkh uhdwl q
i y l h gulyhq whoh huyl h 1 Odqjxdjh Hqjlqhhulqj
Uh xu h 1 HF Whohpdwl 1
kwws=22zzz1 shh kgdw1 uj1
3n1
WORD
STRING
  
3n2+1
WORD
STRING
3n3+2
WORD
STRING
Selec N-Bes Hypo hesis
ENTER
Iljxuh 4= Judppdu qhwz un jhqhudwlqj qqh whg z ug wulqj i glhuhqw ohqjwk
0
1
2
3
4
5
6
1 11 22 42 80 160
QXPEHURIK SRWKHVLV
U
H
P
D
L
Q
L
Q
J

V
W
U
L
Q
J

H
U
U
R
U
V




k=1
k=2
k=5
Iljxuh 5= F psdul q i wkh shu hqw i pl hg uuh w gljlw wulqj d d ixq wl q i wkh qxpehu i judppdu q gh
ndqg wkh qxpehu i psxwhg k|s wkh h 1
0
50
100
150
200
250
300
350
400
1 11 22 42 80 160
QXPEHURIK SRWKHVLV
F
R
P
S
X
W
D
W
L
R
Q
D
O

F
R
V
W


V
H
F
R
Q
G
V

k=1
k=2
k=5
Iljxuh 6= F psdul q i wkh psxwdwl qdo w i wkh su s hg doj ulwkp d d ixq wl q i wkh qxpehu i
judppdu q gh ndqg wkh qxpehu i psxwhg k|s wkh h +Wd n 4,1